home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 24 / AACD 24.iso / AACD / Utilities / ttf2pt1PPC / src / pt1.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-05-27  |  140.4 KB  |  5,967 lines
  1. /*
  2.  * see COPYRIGHT
  3.  */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include <sys/types.h>
  9. #include <sys/stat.h>
  10. #include <fcntl.h>
  11. #include <time.h>
  12. #include <ctype.h>
  13. #include <math.h>
  14.  
  15. #ifndef WINDOWS
  16. #    include <netinet/in.h>
  17. #    include <unistd.h>
  18. #else
  19. #    include "windows.h"
  20. #endif
  21.  
  22. #include "ttf.h"
  23. #include "pt1.h"
  24. #include "global.h"
  25.  
  26. /* big and small values for comparisons */
  27. #define FBIGVAL    (1e20)
  28. #define FEPS    (100000./FBIGVAL)
  29.  
  30. int      stdhw, stdvw;    /* dominant stems widths */
  31. int      stemsnaph[12], stemsnapv[12];    /* most typical stem width */
  32.  
  33. int      bluevalues[14];
  34. int      nblues;
  35. int      otherblues[10];
  36. int      notherb;
  37. int      bbox[4];    /* the FontBBox array */
  38. double   italic_angle;
  39.  
  40. GLYPH   *glyph_list;
  41. int    encoding[ENCTABSZ];    /* inverse of glyph[].char_no */
  42. int    kerning_pairs = 0;
  43.  
  44. /* prototypes */
  45. static int isign( int x);
  46. static int fsign( double x);
  47. static void fixcvdir( GENTRY * ge, int dir);
  48. static void fixcvends( GENTRY * ge);
  49. static int fgetcvdir( GENTRY * ge);
  50. static int igetcvdir( GENTRY * ge);
  51. static int fiszigzag( GENTRY *ge);
  52. static int iiszigzag( GENTRY *ge);
  53. static GENTRY * freethisge( GENTRY *ge);
  54. static void addgeafter( GENTRY *oge, GENTRY *nge );
  55. static GENTRY * newgentry( int flags);
  56. static void debugstems( char *name, STEM * hstems, int nhs, STEM * vstems, int nvs);
  57. static int addbluestems( STEM *s, int n);
  58. static void sortstems( STEM * s, int n);
  59. static int stemoverlap( STEM * s1, STEM * s2);
  60. static int steminblue( STEM *s);
  61. static void markbluestems( STEM *s, int nold);
  62. static int joinmainstems( STEM * s, int nold, int useblues);
  63. static void joinsubstems( STEM * s, short *pairs, int nold, int useblues);
  64. static void fixendpath( GENTRY *ge);
  65. static void fdelsmall( GLYPH *g, double minlen);
  66. static double fcvarea( GENTRY *ge);
  67. static int fckjoinedcv( GLYPH *g, double t, GENTRY *nge, 
  68.     GENTRY *old1, GENTRY *old2, double k);
  69. static double fcvval( GENTRY *ge, int axis, double t);
  70. static double fclosegap( GENTRY *from, GENTRY *to, int axis,
  71.     double gap, double *ret);
  72.  
  73. static int
  74. isign(
  75.      int x
  76. )
  77. {
  78.     if (x > 0)
  79.         return 1;
  80.     else if (x < 0)
  81.         return -1;
  82.     else
  83.         return 0;
  84. }
  85.  
  86. static int
  87. fsign(
  88.      double x
  89. )
  90. {
  91.     if (x > 0.0)
  92.         return 1;
  93.     else if (x < 0.0)
  94.         return -1;
  95.     else
  96.         return 0;
  97. }
  98.  
  99. static GENTRY *
  100. newgentry(
  101.     int flags
  102. )
  103. {
  104.     GENTRY         *ge;
  105.  
  106.     ge = calloc(1, sizeof(GENTRY));
  107.  
  108.     if (ge == 0) {
  109.         fprintf(stderr, "***** Memory allocation error *****\n");
  110.         exit(255);
  111.     }
  112.     ge->stemid = -1;
  113.     ge->flags = flags;
  114.     /* the rest is set to 0 by calloc() */
  115.     return ge;
  116. }
  117.  
  118. /*
  119.  * Routines to print out Postscript functions with optimization
  120.  */
  121.  
  122. void
  123. rmoveto(
  124.     int dx,
  125.     int dy
  126. )
  127. {
  128.     if (optimize && dx == 0)
  129.         fprintf(pfa_file, "%d vmoveto\n", dy);
  130.     else if (optimize && dy == 0)
  131.         fprintf(pfa_file, "%d hmoveto\n", dx);
  132.     else
  133.         fprintf(pfa_file, "%d %d rmoveto\n", dx, dy);
  134. }
  135.  
  136. void
  137. rlineto(
  138.     int dx,
  139.     int dy
  140. )
  141. {
  142.     if (optimize && dx == 0 && dy == 0)    /* for special pathologic
  143.                          * case */
  144.         return;
  145.     else if (optimize && dx == 0)
  146.         fprintf(pfa_file, "%d vlineto\n", dy);
  147.     else if (optimize && dy == 0)
  148.         fprintf(pfa_file, "%d hlineto\n", dx);
  149.     else
  150.         fprintf(pfa_file, "%d %d rlineto\n", dx, dy);
  151. }
  152.  
  153. void
  154. rrcurveto(
  155.       int dx1,
  156.       int dy1,
  157.       int dx2,
  158.       int dy2,
  159.       int dx3,
  160.       int dy3
  161. )
  162. {
  163.     /* first two ifs are for crazy cases that occur surprisingly often */
  164.     if (optimize && dx1 == 0 && dx2 == 0 && dx3 == 0)
  165.         rlineto(0, dy1 + dy2 + dy3);
  166.     else if (optimize && dy1 == 0 && dy2 == 0 && dy3 == 0)
  167.         rlineto(dx1 + dx2 + dx3, 0);
  168.     else if (optimize && dy1 == 0 && dx3 == 0)
  169.         fprintf(pfa_file, "%d %d %d %d hvcurveto\n",
  170.             dx1, dx2, dy2, dy3);
  171.     else if (optimize && dx1 == 0 && dy3 == 0)
  172.         fprintf(pfa_file, "%d %d %d %d vhcurveto\n",
  173.             dy1, dx2, dy2, dx3);
  174.     else
  175.         fprintf(pfa_file, "%d %d %d %d %d %d rrcurveto\n",
  176.             dx1, dy1, dx2, dy2, dx3, dy3);
  177. }
  178.  
  179. void
  180. closepath(void)
  181. {
  182.     fprintf(pfa_file, "closepath\n");
  183. }
  184.  
  185. /*
  186.  * Many of the path processing routines exist (or will exist) in
  187.  * both floating-point and integer version. Fimally most of the
  188.  * processing will go in floating point and the integer processing
  189.  * will become legacy.
  190.  * The names of floating routines start with f, names of integer 
  191.  * routines start with i, and those old routines existing in one 
  192.  * version only have no such prefix at all.
  193.  */
  194.  
  195. /*
  196. ** Routine that checks integrity of the path, for debugging
  197. */
  198.  
  199. void
  200. assertpath(
  201.        GENTRY * from,
  202.        char *file,
  203.        int line,
  204.        char *name
  205. )
  206. {
  207.     GENTRY         *first, *pe, *ge;
  208.     int    isfloat;
  209.  
  210.     if(from==0)
  211.         return;
  212.     isfloat = (from->flags & GEF_FLOAT);
  213.     pe = from->prev;
  214.     for (ge = from; ge != 0; pe = ge, ge = ge->next) {
  215.         if( (ge->flags & GEF_FLOAT) ^ isfloat ) {
  216.             fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
  217.             fprintf(stderr, "float flag changes from %s to %s at 0x%p (type %c, prev type %c)\n",
  218.                 (isfloat ? "TRUE" : "FALSE"), (isfloat ? "FALSE" : "TRUE"), ge, ge->type, pe->type);
  219.             abort();
  220.         }
  221.         if (pe != ge->prev) {
  222.             fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
  223.             fprintf(stderr, "unidirectional chain 0x%x -next-> 0x%x -prev-> 0x%x \n",
  224.                 pe, ge, ge->prev);
  225.             abort();
  226.         }
  227.  
  228.         switch(ge->type) {
  229.         case GE_MOVE:
  230.             break;
  231.         case GE_PATH:
  232.             if (ge->prev == 0) {
  233.                 fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
  234.                 fprintf(stderr, "empty path at 0x%x \n", ge);
  235.                 abort();
  236.             }
  237.             break;
  238.         case GE_LINE:
  239.         case GE_CURVE:
  240.             if(ge->frwd->bkwd != ge) {
  241.                 fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
  242.                 fprintf(stderr, "unidirectional chain 0x%x -frwd-> 0x%x -bkwd-> 0x%x \n",
  243.                     ge, ge->frwd, ge->frwd->bkwd);
  244.                 abort();
  245.             }
  246.             if(ge->prev->type == GE_MOVE) {
  247.                 first = ge;
  248.                 if(ge->bkwd->next->type != GE_PATH) {
  249.                     fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
  250.                     fprintf(stderr, "broken first backlink 0x%x -bkwd-> 0x%x -next-> 0x%x \n",
  251.                         ge, ge->bkwd, ge->bkwd->next);
  252.                     abort();
  253.                 }
  254.             }
  255.             if(ge->next->type == GE_PATH) {
  256.                 if(ge->frwd != first) {
  257.                     fprintf(stderr, "**! assertpath: called from %s line %d (%s) ****\n", file, line, name);
  258.                     fprintf(stderr, "broken loop 0x%x -...-> 0x%x -frwd-> 0x%x \n",
  259.                         first, ge, ge->frwd);
  260.                     abort();
  261.                 }
  262.             }
  263.             break;
  264.         }
  265.  
  266.     }
  267. }
  268.  
  269. void
  270. assertisfloat(
  271.     GLYPH *g,
  272.     char *msg
  273. )
  274. {
  275.     if( !(g->flags & GF_FLOAT) ) {
  276.         fprintf(stderr, "**! Glyph %s is not float: %s\n", g->name, msg);
  277.         abort();
  278.     }
  279.     if(g->lastentry) {
  280.         if( !(g->lastentry->flags & GEF_FLOAT) ) {
  281.             fprintf(stderr, "**! Glyphs %s last entry is int: %s\n", g->name, msg);
  282.             abort();
  283.         }
  284.     }
  285. }
  286.  
  287. void
  288. assertisint(
  289.     GLYPH *g,
  290.     char *msg
  291. )
  292. {
  293.     if( (g->flags & GF_FLOAT) ) {
  294.         fprintf(stderr, "**! Glyph %s is not int: %s\n", g->name, msg);
  295.         abort();
  296.     }
  297.     if(g->lastentry) {
  298.         if( (g->lastentry->flags & GEF_FLOAT) ) {
  299.             fprintf(stderr, "**! Glyphs %s last entry is float: %s\n", g->name, msg);
  300.             abort();
  301.         }
  302.     }
  303. }
  304.  
  305.  
  306. /*
  307.  * Routines to save the generated data about glyph
  308.  */
  309.  
  310. void
  311. fg_rmoveto(
  312.       GLYPH * g,
  313.       double x,
  314.       double y)
  315. {
  316.     GENTRY         *oge;
  317.  
  318.     if (ISDBG(BUILDG))
  319.         fprintf(stderr, "%s: f rmoveto(%g, %g)\n", g->name, x, y);
  320.  
  321.     assertisfloat(g, "adding float MOVE");
  322.  
  323.     if ((oge = g->lastentry) != 0) {
  324.         if (oge->type == GE_MOVE) {    /* just eat up the first move */
  325.             oge->fx3 = x;
  326.             oge->fy3 = y;
  327.         } else if (oge->type == GE_LINE || oge->type == GE_CURVE) {
  328.             fprintf(stderr, "Glyph %s: MOVE in middle of path\n", g->name);
  329.         } else {
  330.             GENTRY         *nge;
  331.  
  332.             nge = newgentry(GEF_FLOAT);
  333.             nge->type = GE_MOVE;
  334.             nge->fx3 = x;
  335.             nge->fy3 = y;
  336.  
  337.             oge->next = nge;
  338.             nge->prev = oge;
  339.             g->lastentry = nge;
  340.         }
  341.     } else {
  342.         GENTRY         *nge;
  343.  
  344.         nge = newgentry(GEF_FLOAT);
  345.         nge->type = GE_MOVE;
  346.         nge->fx3 = x;
  347.         nge->fy3 = y;
  348.         nge->bkwd = (GENTRY*)&g->entries;
  349.         g->entries = g->lastentry = nge;
  350.     }
  351.  
  352.     if (0 && ISDBG(BUILDG))
  353.         dumppaths(g, NULL, NULL);
  354. }
  355.  
  356. void
  357. fg_rlineto(
  358.       GLYPH * g,
  359.       double x,
  360.       double y)
  361. {
  362.     GENTRY         *oge, *nge;
  363.  
  364.     if (ISDBG(BUILDG))
  365.         fprintf(stderr, "%s: f rlineto(%g, %g)\n", g->name, x, y);
  366.  
  367.     assertisfloat(g, "adding float LINE");
  368.  
  369.     nge = newgentry(GEF_FLOAT);
  370.     nge->type = GE_LINE;
  371.     nge->fx3 = x;
  372.     nge->fy3 = y;
  373.  
  374.     if ((oge = g->lastentry) != 0) {
  375.         if (x == oge->fx3 && y == oge->fy3) {    /* empty line */
  376.             /* ignore it or we will get in troubles later */
  377.             free(nge);
  378.             return;
  379.         }
  380.         if (g->path == 0) {
  381.             g->path = nge;
  382.             nge->bkwd = nge->frwd = nge;
  383.         } else {
  384.             oge->frwd = nge;
  385.             nge->bkwd = oge;
  386.             g->path->bkwd = nge;
  387.             nge->frwd = g->path;
  388.         }
  389.  
  390.         oge->next = nge;
  391.         nge->prev = oge;
  392.         g->lastentry = nge;
  393.     } else {
  394.         WARNING_1 fprintf(stderr, "Glyph %s: LINE outside of path\n", g->name);
  395.         free(nge);
  396.     }
  397.  
  398.     if (0 && ISDBG(BUILDG))
  399.         dumppaths(g, NULL, NULL);
  400. }
  401.  
  402. void
  403. fg_rrcurveto(
  404.         GLYPH * g,
  405.         double x1,
  406.         double y1,
  407.         double x2,
  408.         double y2,
  409.         double x3,
  410.         double y3)
  411. {
  412.     GENTRY         *oge, *nge;
  413.  
  414.     oge = g->lastentry;
  415.  
  416.     if (ISDBG(BUILDG))
  417.         fprintf(stderr, "%s: f rrcurveto(%g, %g, %g, %g, %g, %g)\n"
  418.             ,g->name, x1, y1, x2, y2, x3, y3);
  419.  
  420.     assertisfloat(g, "adding float CURVE");
  421.  
  422.     if (oge && oge->fx3 == x1 && x1 == x2 && x2 == x3)    /* check if it's
  423.                                  * actually a line */
  424.         fg_rlineto(g, x1, y3);
  425.     else if (oge && oge->fy3 == y1 && y1 == y2 && y2 == y3)
  426.         fg_rlineto(g, x3, y1);
  427.     else {
  428.         nge = newgentry(GEF_FLOAT);
  429.         nge->type = GE_CURVE;
  430.         nge->fx1 = x1;
  431.         nge->fy1 = y1;
  432.         nge->fx2 = x2;
  433.         nge->fy2 = y2;
  434.         nge->fx3 = x3;
  435.         nge->fy3 = y3;
  436.  
  437.         if (oge != 0) {
  438.             if (x3 == oge->fx3 && y3 == oge->fy3) {
  439.                 free(nge);    /* consider this curve empty */
  440.                 /* ignore it or we will get in troubles later */
  441.                 return;
  442.             }
  443.             if (g->path == 0) {
  444.                 g->path = nge;
  445.                 nge->bkwd = nge->frwd = nge;
  446.             } else {
  447.                 oge->frwd = nge;
  448.                 nge->bkwd = oge;
  449.                 g->path->bkwd = nge;
  450.                 nge->frwd = g->path;
  451.             }
  452.  
  453.             oge->next = nge;
  454.             nge->prev = oge;
  455.             g->lastentry = nge;
  456.         } else {
  457.             WARNING_1 fprintf(stderr, "Glyph %s: CURVE outside of path\n", g->name);
  458.             free(nge);
  459.         }
  460.     }
  461.  
  462.     if (0 && ISDBG(BUILDG))
  463.         dumppaths(g, NULL, NULL);
  464. }
  465.  
  466. void
  467. g_closepath(
  468.         GLYPH * g
  469. )
  470. {
  471.     GENTRY         *oge, *nge;
  472.  
  473.     if (ISDBG(BUILDG))
  474.         fprintf(stderr, "%s: closepath\n", g->name);
  475.  
  476.     oge = g->lastentry;
  477.  
  478.     if (g->path == 0) {
  479.         WARNING_1 fprintf(stderr, "Warning: **** closepath on empty path in glyph \"%s\" ****\n",
  480.             g->name);
  481.         if (oge == 0) {
  482.             WARNING_1 fprintf(stderr, "No previois entry\n");
  483.         } else {
  484.             WARNING_1 fprintf(stderr, "Previous entry type: %c\n", oge->type);
  485.             if (oge->type == GE_MOVE) {
  486.                 g->lastentry = oge->prev;
  487.                 if (oge->prev == 0)
  488.                     g->entries = 0;
  489.             }
  490.         }
  491.         return;
  492.     }
  493.  
  494.     nge = newgentry(oge->flags & GEF_FLOAT); /* keep the same type */
  495.     nge->type = GE_PATH;
  496.  
  497.     g->path = 0;
  498.  
  499.     oge->next = nge;
  500.     nge->prev = oge;
  501.     g->lastentry = nge;
  502.  
  503.     if (0 && ISDBG(BUILDG))
  504.         dumppaths(g, NULL, NULL);
  505. }
  506.  
  507. /*
  508.  * * SB * Routines to smooth and fix the glyphs
  509.  */
  510.  
  511. /*
  512. ** we don't want to see the curves with coinciding middle and
  513. ** outer points
  514. */
  515.  
  516. static void
  517. fixcvends(
  518.       GENTRY * ge
  519. )
  520. {
  521.     int             dx, dy;
  522.     int             x0, y0, x1, y1, x2, y2, x3, y3;
  523.  
  524.     if (ge->type != GE_CURVE)
  525.         return;
  526.  
  527.     if(ge->flags & GEF_FLOAT) {
  528.         fprintf(stderr, "**! fixcvends(0x%x) on floating entry, ABORT\n", ge);
  529.         abort(); /* dump core */
  530.     }
  531.  
  532.     x0 = ge->prev->ix3;
  533.     y0 = ge->prev->iy3;
  534.     x1 = ge->ix1;
  535.     y1 = ge->iy1;
  536.     x2 = ge->ix2;
  537.     y2 = ge->iy2;
  538.     x3 = ge->ix3;
  539.     y3 = ge->iy3;
  540.  
  541.  
  542.     /* look at the start of the curve */
  543.     if (x1 == x0 && y1 == y0) {
  544.         dx = x2 - x1;
  545.         dy = y2 - y1;
  546.  
  547.         if (dx == 0 && dy == 0
  548.             || x2 == x3 && y2 == y3) {
  549.             /* Oops, we actually have a straight line */
  550.             /*
  551.              * if it's small, we hope that it will get optimized
  552.              * later
  553.              */
  554.             if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) {
  555.                 ge->ix1 = x3;
  556.                 ge->iy1 = y3;
  557.                 ge->ix2 = x0;
  558.                 ge->iy2 = y0;
  559.             } else {/* just make it a line */
  560.                 ge->type = GE_LINE;
  561.             }
  562.         } else {
  563.             if (abs(dx) < 4 && abs(dy) < 4) {    /* consider it very
  564.                                  * small */
  565.                 ge->ix1 = x2;
  566.                 ge->iy1 = y2;
  567.             } else if (abs(dx) < 8 && abs(dy) < 8) {    /* consider it small */
  568.                 ge->ix1 += dx / 2;
  569.                 ge->iy1 += dy / 2;
  570.             } else {
  571.                 ge->ix1 += dx / 4;
  572.                 ge->iy1 += dy / 4;
  573.             }
  574.             /* make sure that it's still on the same side */
  575.             if (abs(x3 - x0) * abs(dy) < abs(y3 - y0) * abs(dx)) {
  576.                 if (abs(x3 - x0) * abs(ge->iy1 - y0) > abs(y3 - y0) * abs(ge->ix1 - x0))
  577.                     ge->ix1 += isign(dx);
  578.             } else {
  579.                 if (abs(x3 - x0) * abs(ge->iy1 - y0) < abs(y3 - y0) * abs(ge->ix1 - x0))
  580.                     ge->iy1 += isign(dy);
  581.             }
  582.  
  583.             ge->ix2 += (x3 - x2) / 8;
  584.             ge->iy2 += (y3 - y2) / 8;
  585.             /* make sure that it's still on the same side */
  586.             if (abs(x3 - x0) * abs(y3 - y2) < abs(y3 - y0) * abs(x3 - x2)) {
  587.                 if (abs(x3 - x0) * abs(y3 - ge->iy2) > abs(y3 - y0) * abs(x3 - ge->ix2))
  588.                     ge->iy1 -= isign(y3 - y2);
  589.             } else {
  590.                 if (abs(x3 - x0) * abs(y3 - ge->iy2) < abs(y3 - y0) * abs(x3 - ge->ix2))
  591.                     ge->ix1 -= isign(x3 - x2);
  592.             }
  593.  
  594.         }
  595.     } else if (x2 == x3 && y2 == y3) {
  596.         dx = x1 - x2;
  597.         dy = y1 - y2;
  598.  
  599.         if (dx == 0 && dy == 0) {
  600.             /* Oops, we actually have a straight line */
  601.             /*
  602.              * if it's small, we hope that it will get optimized
  603.              * later
  604.              */
  605.             if (abs(x3 - x0) <= 2 || abs(y3 - y0) <= 2) {
  606.                 ge->ix1 = x3;
  607.                 ge->iy1 = y3;
  608.                 ge->ix2 = x0;
  609.                 ge->iy2 = y0;
  610.             } else {/* just make it a line */
  611.                 ge->type = GE_LINE;
  612.             }
  613.         } else {
  614.             if (abs(dx) < 4 && abs(dy) < 4) {    /* consider it very
  615.                                  * small */
  616.                 ge->ix2 = x1;
  617.                 ge->iy2 = y1;
  618.             } else if (abs(dx) < 8 && abs(dy) < 8) {    /* consider it small */
  619.                 ge->ix2 += dx / 2;
  620.                 ge->iy2 += dy / 2;
  621.             } else {
  622.                 ge->ix2 += dx / 4;
  623.                 ge->iy2 += dy / 4;
  624.             }
  625.             /* make sure that it's still on the same side */
  626.             if (abs(x3 - x0) * abs(dy) < abs(y3 - y0) * abs(dx)) {
  627.                 if (abs(x3 - x0) * abs(ge->iy2 - y3) > abs(y3 - y0) * abs(ge->ix2 - x3))
  628.                     ge->ix2 += isign(dx);
  629.             } else {
  630.                 if (abs(x3 - x0) * abs(ge->iy2 - y3) < abs(y3 - y0) * abs(ge->ix2 - x3))
  631.                     ge->iy2 += isign(dy);
  632.             }
  633.  
  634.             ge->ix1 += (x0 - x1) / 8;
  635.             ge->iy1 += (y0 - y1) / 8;
  636.             /* make sure that it's still on the same side */
  637.             if (abs(x3 - x0) * abs(y0 - y1) < abs(y3 - y0) * abs(x0 - x1)) {
  638.                 if (abs(x3 - x0) * abs(y0 - ge->iy1) > abs(y3 - y0) * abs(x0 - ge->ix1))
  639.                     ge->iy1 -= isign(y0 - y1);
  640.             } else {
  641.                 if (abs(x3 - x0) * abs(y0 - ge->iy1) < abs(y3 - y0) * abs(x0 - ge->ix1))
  642.                     ge->ix1 -= isign(x0 - x1);
  643.             }
  644.  
  645.         }
  646.     }
  647. }
  648.  
  649. /* if we have any curves that are in fact flat but
  650. ** are not horizontal nor vertical, substitute
  651. ** them also with lines
  652. */
  653.  
  654. void
  655. flattencurves(
  656.           GLYPH * g
  657. )
  658. {
  659.     GENTRY         *ge;
  660.     int             x0, y0, x1, y1, x2, y2, x3, y3;
  661.  
  662.     assertisint(g, "flattencurves INT");
  663.  
  664.     for (ge = g->entries; ge != 0; ge = ge->next) {
  665.         if (ge->type != GE_CURVE)
  666.             continue;
  667.  
  668.         x0 = ge->prev->ix3;
  669.         y0 = ge->prev->iy3;
  670.         x1 = ge->ix1;
  671.         y1 = ge->iy1;
  672.         x2 = ge->ix2;
  673.         y2 = ge->iy2;
  674.         x3 = ge->ix3;
  675.         y3 = ge->iy3;
  676.  
  677.         if ((x1 - x0) * (y2 - y1) == (x2 - x1) * (y1 - y0)
  678.             && (x1 - x0) * (y3 - y2) == (x3 - x2) * (y1 - y0)) {
  679.             ge->type = GE_LINE;
  680.         }
  681.     }
  682. }
  683.  
  684. /*
  685. ** After transformations we want to make sure that the resulting
  686. ** curve is going in the same quadrant as the original one,
  687. ** because rounding errors introduced during transformations
  688. ** may make the result completeley wrong.
  689. **
  690. ** `dir' argument describes the direction of the original curve,
  691. ** it is the superposition of two values for the front and
  692. ** rear ends of curve:
  693. **
  694. ** >EQUAL - goes over the line connecting the ends
  695. ** =EQUAL - coincides with the line connecting the ends
  696. ** <EQUAL - goes under the line connecting the ends
  697. **
  698. ** See CVDIR_* for exact definitions.
  699. */
  700.  
  701. static void
  702. fixcvdir(
  703.      GENTRY * ge,
  704.      int dir
  705. )
  706. {
  707.     int             a, b, c, d;
  708.     double          kk, kk1, kk2;
  709.     int             changed;
  710.     int             fdir, rdir;
  711.  
  712.     if(ge->flags & GEF_FLOAT) {
  713.         fprintf(stderr, "**! fixcvdir(0x%x) on floating entry, ABORT\n", ge);
  714.         abort(); /* dump core */
  715.     }
  716.  
  717.     fdir = (dir & CVDIR_FRONT) - CVDIR_FEQUAL;
  718.     if ((dir & CVDIR_REAR) == CVDIR_RSAME)
  719.         rdir = fdir; /* we need only isign, exact value doesn't matter */
  720.     else
  721.         rdir = (dir & CVDIR_REAR) - CVDIR_REQUAL;
  722.  
  723.     fixcvends(ge);
  724.  
  725.     c = isign(ge->ix3 - ge->prev->ix3);    /* note the direction of
  726.                          * curve */
  727.     d = isign(ge->iy3 - ge->prev->iy3);
  728.  
  729.     a = ge->iy3 - ge->prev->iy3;
  730.     b = ge->ix3 - ge->prev->ix3;
  731.     kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  732.     a = ge->iy1 - ge->prev->iy3;
  733.     b = ge->ix1 - ge->prev->ix3;
  734.     kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  735.     a = ge->iy3 - ge->iy2;
  736.     b = ge->ix3 - ge->ix2;
  737.     kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  738.  
  739.     changed = 1;
  740.     while (changed) {
  741.         if (ISDBG(FIXCVDIR)) {
  742.             /* for debugging */
  743.             fprintf(stderr, "fixcvdir %d %d (%d %d %d %d %d %d) %f %f %f\n",
  744.                 fdir, rdir,
  745.                 ge->ix1 - ge->prev->ix3,
  746.                 ge->iy1 - ge->prev->iy3,
  747.                 ge->ix2 - ge->ix1,
  748.                 ge->iy2 - ge->iy1,
  749.                 ge->ix3 - ge->ix2,
  750.                 ge->iy3 - ge->iy2,
  751.                 kk1, kk, kk2);
  752.         }
  753.         changed = 0;
  754.  
  755.         if (fdir > 0) {
  756.             if (kk1 > kk) {    /* the front end has problems */
  757.                 if (c * (ge->ix1 - ge->prev->ix3) > 0) {
  758.                     ge->ix1 -= c;
  759.                     changed = 1;
  760.                 } if (d * (ge->iy2 - ge->iy1) > 0) {
  761.                     ge->iy1 += d;
  762.                     changed = 1;
  763.                 }
  764.                 /* recalculate the coefficients */
  765.                 a = ge->iy3 - ge->prev->iy3;
  766.                 b = ge->ix3 - ge->prev->ix3;
  767.                 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  768.                 a = ge->iy1 - ge->prev->iy3;
  769.                 b = ge->ix1 - ge->prev->ix3;
  770.                 kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  771.             }
  772.         } else if (fdir < 0) {
  773.             if (kk1 < kk) {    /* the front end has problems */
  774.                 if (c * (ge->ix2 - ge->ix1) > 0) {
  775.                     ge->ix1 += c;
  776.                     changed = 1;
  777.                 } if (d * (ge->iy1 - ge->prev->iy3) > 0) {
  778.                     ge->iy1 -= d;
  779.                     changed = 1;
  780.                 }
  781.                 /* recalculate the coefficients */
  782.                 a = ge->iy1 - ge->prev->iy3;
  783.                 b = ge->ix1 - ge->prev->ix3;
  784.                 kk1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  785.                 a = ge->iy3 - ge->prev->iy3;
  786.                 b = ge->ix3 - ge->prev->ix3;
  787.                 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  788.             }
  789.         }
  790.         if (rdir > 0) {
  791.             if (kk2 < kk) {    /* the rear end has problems */
  792.                 if (c * (ge->ix2 - ge->ix1) > 0) {
  793.                     ge->ix2 -= c;
  794.                     changed = 1;
  795.                 } if (d * (ge->iy3 - ge->iy2) > 0) {
  796.                     ge->iy2 += d;
  797.                     changed = 1;
  798.                 }
  799.                 /* recalculate the coefficients */
  800.                 a = ge->iy3 - ge->prev->iy3;
  801.                 b = ge->ix3 - ge->prev->ix3;
  802.                 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  803.                 a = ge->iy3 - ge->iy2;
  804.                 b = ge->ix3 - ge->ix2;
  805.                 kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  806.             }
  807.         } else if (rdir < 0) {
  808.             if (kk2 > kk) {    /* the rear end has problems */
  809.                 if (c * (ge->ix3 - ge->ix2) > 0) {
  810.                     ge->ix2 += c;
  811.                     changed = 1;
  812.                 } if (d * (ge->iy2 - ge->iy1) > 0) {
  813.                     ge->iy2 -= d;
  814.                     changed = 1;
  815.                 }
  816.                 /* recalculate the coefficients */
  817.                 a = ge->iy3 - ge->prev->iy3;
  818.                 b = ge->ix3 - ge->prev->ix3;
  819.                 kk = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  820.                 a = ge->iy3 - ge->iy2;
  821.                 b = ge->ix3 - ge->ix2;
  822.                 kk2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  823.             }
  824.         }
  825.     }
  826.     fixcvends(ge);
  827. }
  828.  
  829. /* Get the directions of ends of curve for further usage */
  830.  
  831. /* expects that the previous element is also float */
  832.  
  833. static int
  834. fgetcvdir(
  835.      GENTRY * ge
  836. )
  837. {
  838.     double          a, b;
  839.     double          k, k1, k2;
  840.     int             dir = 0;
  841.  
  842.     if( !(ge->flags & GEF_FLOAT) ) {
  843.         fprintf(stderr, "**! fgetcvdir(0x%x) on int entry, ABORT\n", ge);
  844.         abort(); /* dump core */
  845.     }
  846.  
  847.     a = ge->fy3 - ge->prev->fy3;
  848.     b = ge->fx3 - ge->prev->fx3;
  849.     k = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ( b / a));
  850.     a = ge->fy1 - ge->prev->fy3;
  851.     b = ge->fx1 - ge->prev->fx3;
  852.     k1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ( b / a));
  853.     a = ge->fy3 - ge->fy2;
  854.     b = ge->fx3 - ge->fx2;
  855.     k2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ( b / a));
  856.  
  857.     if (k1 < k)
  858.         dir |= CVDIR_FUP;
  859.     else if (k1 > k)
  860.         dir |= CVDIR_FDOWN;
  861.     else
  862.         dir |= CVDIR_FEQUAL;
  863.  
  864.     if (k2 > k)
  865.         dir |= CVDIR_RUP;
  866.     else if (k2 < k)
  867.         dir |= CVDIR_RDOWN;
  868.     else
  869.         dir |= CVDIR_REQUAL;
  870.  
  871.     return dir;
  872. }
  873.  
  874.  
  875. /* expects that the previous element is also int */
  876.  
  877. static int
  878. igetcvdir(
  879.      GENTRY * ge
  880. )
  881. {
  882.     int             a, b;
  883.     double          k, k1, k2;
  884.     int             dir = 0;
  885.  
  886.     if(ge->flags & GEF_FLOAT) {
  887.         fprintf(stderr, "**! igetcvdir(0x%x) on floating entry, ABORT\n", ge);
  888.         abort(); /* dump core */
  889.     }
  890.  
  891.     a = ge->iy3 - ge->prev->iy3;
  892.     b = ge->ix3 - ge->prev->ix3;
  893.     k = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  894.     a = ge->iy1 - ge->prev->iy3;
  895.     b = ge->ix1 - ge->prev->ix3;
  896.     k1 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  897.     a = ge->iy3 - ge->iy2;
  898.     b = ge->ix3 - ge->ix2;
  899.     k2 = fabs(a == 0 ? (b == 0 ? 1. : 100000.) : ((double) b / (double) a));
  900.  
  901.     if (k1 < k)
  902.         dir |= CVDIR_FUP;
  903.     else if (k1 > k)
  904.         dir |= CVDIR_FDOWN;
  905.     else
  906.         dir |= CVDIR_FEQUAL;
  907.  
  908.     if (k2 > k)
  909.         dir |= CVDIR_RUP;
  910.     else if (k2 < k)
  911.         dir |= CVDIR_RDOWN;
  912.     else
  913.         dir |= CVDIR_REQUAL;
  914.  
  915.     return dir;
  916. }
  917.  
  918. #if 0
  919. /* a function just to test the work of fixcvdir() */
  920. static void
  921. testfixcvdir(
  922.          GLYPH * g
  923. )
  924. {
  925.     GENTRY         *ge;
  926.     int             dir;
  927.  
  928.     for (ge = g->entries; ge != 0; ge = ge->next) {
  929.         if (ge->type == GE_CURVE) {
  930.             dir = igetcvdir(ge);
  931.             fixcvdir(ge, dir);
  932.         }
  933.     }
  934. }
  935. #endif
  936.  
  937. static int
  938. iround(
  939.     double val
  940. )
  941. {
  942.     return (int) (val > 0 ? val + 0.5 : val - 0.5);
  943. }
  944.     
  945. /* for debugging - dump the glyph
  946.  * mark with a star the entries from start to end inclusive
  947.  * (start == NULL means don't mark any, end == NULL means to the last)
  948.  */
  949.  
  950. void
  951. dumppaths(
  952.     GLYPH *g,
  953.     GENTRY *start,
  954.     GENTRY *end
  955. )
  956. {
  957.     GENTRY *ge;
  958.     int i;
  959.     char mark=' ';
  960.  
  961.     fprintf(stderr, "Glyph %s:\n", g->name);
  962.  
  963.     /* now do the conversion */
  964.     for(ge = g->entries; ge != 0; ge = ge->next) {
  965.         if(ge == start)
  966.             mark = '*';
  967.         fprintf(stderr, " %c %8x", mark, ge);
  968.         switch(ge->type) {
  969.         case GE_MOVE:
  970.         case GE_LINE:
  971.             if(ge->flags & GEF_FLOAT)
  972.                 fprintf(stderr," %c float (%g, %g)\n", ge->type, ge->fx3, ge->fy3);
  973.             else
  974.                 fprintf(stderr," %c int (%d, %d)\n", ge->type, ge->ix3, ge->iy3);
  975.             break;
  976.         case GE_CURVE:
  977.             if(ge->flags & GEF_FLOAT) {
  978.                 fprintf(stderr," C float ");
  979.                 for(i=0; i<3; i++)
  980.                     fprintf(stderr,"(%g, %g) ", ge->fxn[i], ge->fyn[i]);
  981.                 fprintf(stderr,"\n");
  982.             } else {
  983.                 fprintf(stderr," C int ");
  984.                 for(i=0; i<3; i++)
  985.                     fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
  986.                 fprintf(stderr,"\n");
  987.             }
  988.             break;
  989.         default:
  990.             fprintf(stderr, " %c\n", ge->type);
  991.             break;
  992.         }
  993.         if(ge == end)
  994.             mark = ' ';
  995.     }
  996. }
  997.  
  998. /*
  999.  * Routine that converts all entries in the path from float to int
  1000.  */
  1001.  
  1002. void
  1003. pathtoint(
  1004.     GLYPH *g
  1005. )
  1006. {
  1007.     GENTRY *ge;
  1008.     int x[3], y[3];
  1009.     int i;
  1010.  
  1011.  
  1012.     if(ISDBG(TOINT))
  1013.         fprintf(stderr, "TOINT: glyph %s\n", g->name);
  1014.     assertisfloat(g, "converting path to int\n");
  1015.  
  1016.     fdelsmall(g, 1.0); /* get rid of sub-pixel contours */
  1017.     assertpath(g->entries, __FILE__, __LINE__, g->name);
  1018.  
  1019.     /* 1st pass, collect the directions of the curves: have
  1020.      * to do that in advance, while everyting is float
  1021.      */
  1022.     for(ge = g->entries; ge != 0; ge = ge->next) {
  1023.         if( !(ge->flags & GEF_FLOAT) ) {
  1024.             fprintf(stderr, "**! glyphs %s has int entry, found in conversion to int\n",
  1025.                 g->name);
  1026.             exit(1);
  1027.         }
  1028.         if(ge->type == GE_CURVE) {
  1029.             ge->dir = fgetcvdir(ge);
  1030.         }
  1031.     }
  1032.  
  1033.     /* now do the conversion */
  1034.     for(ge = g->entries; ge != 0; ge = ge->next) {
  1035.         switch(ge->type) {
  1036.         case GE_MOVE:
  1037.         case GE_LINE:
  1038.             if(ISDBG(TOINT))
  1039.                 fprintf(stderr," %c float x=%g y=%g\n", ge->type, ge->fx3, ge->fy3);
  1040.             x[0] = iround(ge->fx3);
  1041.             y[0] = iround(ge->fy3);
  1042.             for(i=0; i<3; i++) { /* put some valid values everywhere, for convenience */
  1043.                 ge->ixn[i] = x[0];
  1044.                 ge->iyn[i] = y[0];
  1045.             }
  1046.             if(ISDBG(TOINT))
  1047.                 fprintf(stderr,"   int   x=%d y=%d\n", ge->ix3, ge->iy3);
  1048.             break;
  1049.         case GE_CURVE:
  1050.             if(ISDBG(TOINT))
  1051.                 fprintf(stderr," %c float ", ge->type);
  1052.  
  1053.             for(i=0; i<3; i++) {
  1054.                 if(ISDBG(TOINT))
  1055.                     fprintf(stderr,"(%g, %g) ", ge->fxn[i], ge->fyn[i]);
  1056.                 x[i] = iround(ge->fxn[i]);
  1057.                 y[i] = iround(ge->fyn[i]);
  1058.             }
  1059.  
  1060.             if(ISDBG(TOINT))
  1061.                 fprintf(stderr,"\n   int   ");
  1062.  
  1063.             for(i=0; i<3; i++) {
  1064.                 ge->ixn[i] = x[i];
  1065.                 ge->iyn[i] = y[i];
  1066.                 if(ISDBG(TOINT))
  1067.                     fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
  1068.             }
  1069.             ge->flags &= ~GEF_FLOAT; /* for fixcvdir */
  1070.             fixcvdir(ge, ge->dir);
  1071.  
  1072.             if(ISDBG(TOINT)) {
  1073.                 fprintf(stderr,"\n   fixed ");
  1074.                 for(i=0; i<3; i++)
  1075.                     fprintf(stderr,"(%d, %d) ", ge->ixn[i], ge->iyn[i]);
  1076.                 fprintf(stderr,"\n");
  1077.             }
  1078.  
  1079.             break;
  1080.         }
  1081.         ge->flags &= ~GEF_FLOAT;
  1082.     }
  1083.     g->flags &= ~GF_FLOAT;
  1084. }
  1085.  
  1086.  
  1087. /* check whether we can fix up the curve to change its size by (dx,dy) */
  1088. /* 0 means NO, 1 means YES */
  1089.  
  1090. /* for float: if scaling would be under 10% */
  1091.  
  1092. int
  1093. fcheckcv(
  1094.     GENTRY * ge,
  1095.     double dx,
  1096.     double dy
  1097. )
  1098. {
  1099.     if( !(ge->flags & GEF_FLOAT) ) {
  1100.         fprintf(stderr, "**! fcheckcv(0x%x) on int entry, ABORT\n", ge);
  1101.         abort(); /* dump core */
  1102.     }
  1103.  
  1104.     if (ge->type != GE_CURVE)
  1105.         return 0;
  1106.  
  1107.     if( fabs(ge->fx3 - ge->prev->fx3) < fabs(dx) * 10 )
  1108.         return 0;
  1109.  
  1110.     if( fabs(ge->fy3 - ge->prev->fy3) < fabs(dy) * 10 )
  1111.         return 0;
  1112.  
  1113.     return 1;
  1114. }
  1115.  
  1116. /* for int: if won't create new zigzags at the ends */
  1117.  
  1118. int
  1119. icheckcv(
  1120.     GENTRY * ge,
  1121.     int dx,
  1122.     int dy
  1123. )
  1124. {
  1125.     int             xdep, ydep;
  1126.  
  1127.     if(ge->flags & GEF_FLOAT) {
  1128.         fprintf(stderr, "**! icheckcv(0x%x) on floating entry, ABORT\n", ge);
  1129.         abort(); /* dump core */
  1130.     }
  1131.  
  1132.     if (ge->type != GE_CURVE)
  1133.         return 0;
  1134.  
  1135.     xdep = ge->ix3 - ge->prev->ix3;
  1136.     ydep = ge->iy3 - ge->prev->iy3;
  1137.  
  1138.     if (ge->type == GE_CURVE
  1139.         && (xdep * (xdep + dx)) > 0
  1140.         && (ydep * (ydep + dy)) > 0) {
  1141.         return 1;
  1142.     } else
  1143.         return 0;
  1144. }
  1145.  
  1146. /* float connect the ends of open contours */
  1147.  
  1148. void
  1149. fclosepaths(
  1150.        GLYPH * g
  1151. )
  1152. {
  1153.     GENTRY         *ge, *fge, *xge, *nge;
  1154.     int             i;
  1155.  
  1156.     assertisfloat(g, "fclosepaths float\n");
  1157.  
  1158.     for (xge = g->entries; xge != 0; xge = xge->next) {
  1159.         if( xge->type != GE_PATH )
  1160.             continue;
  1161.  
  1162.         ge = xge->prev;
  1163.         if(ge == 0 || ge->type != GE_LINE && ge->type!= GE_CURVE) {
  1164.             fprintf(stderr, "**! Glyph %s got empty path\n",
  1165.                 g->name);
  1166.             exit(1);
  1167.         }
  1168.  
  1169.         fge = ge->frwd;
  1170.         if (fge->prev == 0 || fge->prev->type != GE_MOVE) {
  1171.             fprintf(stderr, "**! Glyph %s got strange beginning of path\n",
  1172.                 g->name);
  1173.             exit(1);
  1174.         }
  1175.         fge = fge->prev;
  1176.         if (fge->fx3 != ge->fx3 || fge->fy3 != ge->fy3) {
  1177.             /* we have to fix this open path */
  1178.  
  1179.             WARNING_4 fprintf(stderr, "Glyph %s got path open by dx=%g dy=%g\n",
  1180.             g->name, fge->fx3 - ge->fx3, fge->fy3 - ge->fy3);
  1181.  
  1182.  
  1183.             /* add a new line */
  1184.             nge = newgentry(GEF_FLOAT);
  1185.             (*nge) = (*ge);
  1186.             nge->fx3 = fge->fx3;
  1187.             nge->fy3 = fge->fy3;
  1188.             nge->type = GE_LINE;
  1189.  
  1190.             addgeafter(ge, nge);
  1191.  
  1192.             if (fabs(ge->fx3 - fge->fx3) <= 2 && fabs(ge->fy3 - fge->fy3) <= 2) {
  1193.                 /*
  1194.                  * small change, try to get rid of the new entry
  1195.                  */
  1196.  
  1197.                 double df[2];
  1198.  
  1199.                 for(i=0; i<2; i++) {
  1200.                     df[i] = ge->fpoints[i][2] - fge->fpoints[i][2];
  1201.                     df[i] = fclosegap(nge, nge, i, df[i], NULL);
  1202.                 }
  1203.  
  1204.                 if(df[0] == 0. && df[1] == 0.) {
  1205.                     /* closed gap successfully, remove the added entry */
  1206.                     freethisge(nge);
  1207.                 }
  1208.             }
  1209.         }
  1210.     }
  1211. }
  1212.  
  1213. void
  1214. smoothjoints(
  1215.          GLYPH * g
  1216. )
  1217. {
  1218.     GENTRY         *ge, *ne;
  1219.     int             dx1, dy1, dx2, dy2, k;
  1220.     int             dir;
  1221.  
  1222.     return; /* this stuff seems to create problems */
  1223.  
  1224.     assertisint(g, "smoothjoints int");
  1225.  
  1226.     if (g->entries == 0)    /* nothing to do */
  1227.         return;
  1228.  
  1229.     for (ge = g->entries->next; ge != 0; ge = ge->next) {
  1230.         ne = ge->frwd;
  1231.  
  1232.         /*
  1233.          * although there should be no one-line path * and any path
  1234.          * must end with CLOSEPATH, * nobody can say for sure
  1235.          */
  1236.  
  1237.         if (ge == ne || ne == 0)
  1238.             continue;
  1239.  
  1240.         /* now handle various joints */
  1241.  
  1242.         if (ge->type == GE_LINE && ne->type == GE_LINE) {
  1243.             dx1 = ge->ix3 - ge->prev->ix3;
  1244.             dy1 = ge->iy3 - ge->prev->iy3;
  1245.             dx2 = ne->ix3 - ge->ix3;
  1246.             dy2 = ne->iy3 - ge->iy3;
  1247.  
  1248.             /* check whether they have the same direction */
  1249.             /* and the same slope */
  1250.             /* then we can join them into one line */
  1251.  
  1252.             if (dx1 * dx2 >= 0 && dy1 * dy2 >= 0 && dx1 * dy2 == dy1 * dx2) {
  1253.                 /* extend the previous line */
  1254.                 ge->ix3 = ne->ix3;
  1255.                 ge->iy3 = ne->iy3;
  1256.  
  1257.                 /* and get rid of the next line */
  1258.                 freethisge(ne);
  1259.             }
  1260.         } else if (ge->type == GE_LINE && ne->type == GE_CURVE) {
  1261.             fixcvends(ne);
  1262.  
  1263.             dx1 = ge->ix3 - ge->prev->ix3;
  1264.             dy1 = ge->iy3 - ge->prev->iy3;
  1265.             dx2 = ne->ix1 - ge->ix3;
  1266.             dy2 = ne->iy1 - ge->iy3;
  1267.  
  1268.             /* if the line is nearly horizontal and we can fix it */
  1269.             if (dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0
  1270.                 && icheckcv(ne, 0, -dy1)
  1271.                 && abs(dy1) <= 4) {
  1272.                 dir = igetcvdir(ne);
  1273.                 ge->iy3 -= dy1;
  1274.                 ne->iy1 -= dy1;
  1275.                 fixcvdir(ne, dir);
  1276.                 if (ge->next != ne)
  1277.                     ne->prev->iy3 -= dy1;
  1278.                 dy1 = 0;
  1279.             } else if (dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0
  1280.                    && icheckcv(ne, -dx1, 0)
  1281.                    && abs(dx1) <= 4) {
  1282.                 /* the same but vertical */
  1283.                 dir = igetcvdir(ne);
  1284.                 ge->ix3 -= dx1;
  1285.                 ne->ix1 -= dx1;
  1286.                 fixcvdir(ne, dir);
  1287.                 if (ge->next != ne)
  1288.                     ne->prev->ix3 -= dx1;
  1289.                 dx1 = 0;
  1290.             }
  1291.             /*
  1292.              * if line is horizontal and curve begins nearly
  1293.              * horizontally
  1294.              */
  1295.             if (dy1 == 0 && dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0) {
  1296.                 dir = igetcvdir(ne);
  1297.                 ne->iy1 -= dy2;
  1298.                 fixcvdir(ne, dir);
  1299.                 dy2 = 0;
  1300.             } else if (dx1 == 0 && dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0) {
  1301.                 /* the same but vertical */
  1302.                 dir = igetcvdir(ne);
  1303.                 ne->ix1 -= dx2;
  1304.                 fixcvdir(ne, dir);
  1305.                 dx2 = 0;
  1306.             }
  1307.         } else if (ge->type == GE_CURVE && ne->type == GE_LINE) {
  1308.             fixcvends(ge);
  1309.  
  1310.             dx1 = ge->ix3 - ge->ix2;
  1311.             dy1 = ge->iy3 - ge->iy2;
  1312.             dx2 = ne->ix3 - ge->ix3;
  1313.             dy2 = ne->iy3 - ge->iy3;
  1314.  
  1315.             /* if the line is nearly horizontal and we can fix it */
  1316.             if (dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0
  1317.                 && icheckcv(ge, 0, dy2)
  1318.                 && abs(dy2) <= 4) {
  1319.                 dir = igetcvdir(ge);
  1320.                 ge->iy3 += dy2;
  1321.                 ge->iy2 += dy2;
  1322.                 fixcvdir(ge, dir);
  1323.                 if (ge->next != ne)
  1324.                     ne->prev->iy3 += dy2;
  1325.                 dy2 = 0;
  1326.             } else if (dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0
  1327.                    && icheckcv(ge, dx2, 0)
  1328.                    && abs(dx2) <= 4) {
  1329.                 /* the same but vertical */
  1330.                 dir = igetcvdir(ge);
  1331.                 ge->ix3 += dx2;
  1332.                 ge->ix2 += dx2;
  1333.                 fixcvdir(ge, dir);
  1334.                 if (ge->next != ne)
  1335.                     ne->prev->ix3 += dx2;
  1336.                 dx2 = 0;
  1337.             }
  1338.             /*
  1339.              * if line is horizontal and curve ends nearly
  1340.              * horizontally
  1341.              */
  1342.             if (dy2 == 0 && dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0) {
  1343.                 dir = igetcvdir(ge);
  1344.                 ge->iy2 += dy1;
  1345.                 fixcvdir(ge, dir);
  1346.                 dy1 = 0;
  1347.             } else if (dx2 == 0 && dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0) {
  1348.                 /* the same but vertical */
  1349.                 dir = igetcvdir(ge);
  1350.                 ge->ix2 += dx1;
  1351.                 fixcvdir(ge, dir);
  1352.                 dx1 = 0;
  1353.             }
  1354.         } else if (ge->type == GE_CURVE && ne->type == GE_CURVE) {
  1355.             fixcvends(ge);
  1356.             fixcvends(ne);
  1357.  
  1358.             dx1 = ge->ix3 - ge->ix2;
  1359.             dy1 = ge->iy3 - ge->iy2;
  1360.             dx2 = ne->ix1 - ge->ix3;
  1361.             dy2 = ne->iy1 - ge->iy3;
  1362.  
  1363.             /*
  1364.              * check if we have a rather smooth joint at extremal
  1365.              * point
  1366.              */
  1367.             /* left or right extremal point */
  1368.             if (abs(dx1) <= 4 && abs(dx2) <= 4
  1369.                 && dy1 != 0 && 5 * abs(dx1) / abs(dy1) == 0
  1370.                 && dy2 != 0 && 5 * abs(dx2) / abs(dy2) == 0
  1371.                 && (ge->iy3 < ge->prev->iy3 && ne->iy3 < ge->iy3
  1372.                 || ge->iy3 > ge->prev->iy3 && ne->iy3 > ge->iy3)
  1373.               && (ge->ix3 - ge->prev->ix3) * (ne->ix3 - ge->ix3) < 0
  1374.                 ) {
  1375.                 dir = igetcvdir(ge);
  1376.                 ge->ix2 += dx1;
  1377.                 dx1 = 0;
  1378.                 fixcvdir(ge, dir);
  1379.                 dir = igetcvdir(ne);
  1380.                 ne->ix1 -= dx2;
  1381.                 dx2 = 0;
  1382.                 fixcvdir(ne, dir);
  1383.             }
  1384.             /* top or down extremal point */
  1385.             else if (abs(dy1) <= 4 && abs(dy2) <= 4
  1386.                  && dx1 != 0 && 5 * abs(dy1) / abs(dx1) == 0
  1387.                  && dx2 != 0 && 5 * abs(dy2) / abs(dx2) == 0
  1388.                  && (ge->ix3 < ge->prev->ix3 && ne->ix3 < ge->ix3
  1389.                 || ge->ix3 > ge->prev->ix3 && ne->ix3 > ge->ix3)
  1390.                  && (ge->iy3 - ge->prev->iy3) * (ne->iy3 - ge->iy3) < 0
  1391.                 ) {
  1392.                 dir = igetcvdir(ge);
  1393.                 ge->iy2 += dy1;
  1394.                 dy1 = 0;
  1395.                 fixcvdir(ge, dir);
  1396.                 dir = igetcvdir(ne);
  1397.                 ne->iy1 -= dy2;
  1398.                 dy2 = 0;
  1399.                 fixcvdir(ne, dir);
  1400.             }
  1401.             /* or may be we just have a smooth junction */
  1402.             else if (dx1 * dx2 >= 0 && dy1 * dy2 >= 0
  1403.                  && 10 * abs(k = abs(dx1 * dy2) - abs(dy1 * dx2)) < (abs(dx1 * dy2) + abs(dy1 * dx2))) {
  1404.                 int             tries[6][4];
  1405.                 int             results[6];
  1406.                 int             i, b;
  1407.  
  1408.                 /* build array of changes we are going to try */
  1409.                 /* uninitalized entries are 0 */
  1410.                 if (k > 0) {
  1411.                     static int      t1[6][4] = {
  1412.                         {0, 0, 0, 0},
  1413.                         {-1, 0, 1, 0},
  1414.                         {-1, 0, 0, 1},
  1415.                         {0, -1, 1, 0},
  1416.                         {0, -1, 0, 1},
  1417.                     {-1, -1, 1, 1}};
  1418.                     memcpy(tries, t1, sizeof tries);
  1419.                 } else {
  1420.                     static int      t1[6][4] = {
  1421.                         {0, 0, 0, 0},
  1422.                         {1, 0, -1, 0},
  1423.                         {1, 0, 0, -1},
  1424.                         {0, 1, -1, 0},
  1425.                         {0, 1, 0, -1},
  1426.                     {1, 1, -1, -1}};
  1427.                     memcpy(tries, t1, sizeof tries);
  1428.                 }
  1429.  
  1430.                 /* now try the changes */
  1431.                 results[0] = abs(k);
  1432.                 for (i = 1; i < 6; i++) {
  1433.                     results[i] = abs((abs(dx1) + tries[i][0]) * (abs(dy2) + tries[i][1]) -
  1434.                              (abs(dy1) + tries[i][2]) * (abs(dx2) + tries[i][3]));
  1435.                 }
  1436.  
  1437.                 /* and find the best try */
  1438.                 k = abs(k);
  1439.                 b = 0;
  1440.                 for (i = 1; i < 6; i++)
  1441.                     if (results[i] < k) {
  1442.                         k = results[i];
  1443.                         b = i;
  1444.                     }
  1445.                 /* and finally apply it */
  1446.                 if (dx1 < 0)
  1447.                     tries[b][0] = -tries[b][0];
  1448.                 if (dy2 < 0)
  1449.                     tries[b][1] = -tries[b][1];
  1450.                 if (dy1 < 0)
  1451.                     tries[b][2] = -tries[b][2];
  1452.                 if (dx2 < 0)
  1453.                     tries[b][3] = -tries[b][3];
  1454.  
  1455.                 dir = igetcvdir(ge);
  1456.                 ge->ix2 -= tries[b][0];
  1457.                 ge->iy2 -= tries[b][2];
  1458.                 fixcvdir(ge, dir);
  1459.                 dir = igetcvdir(ne);
  1460.                 ne->ix1 += tries[b][3];
  1461.                 ne->iy1 += tries[b][1];
  1462.                 fixcvdir(ne, dir);
  1463.             }
  1464.         }
  1465.     }
  1466. }
  1467.  
  1468. /* debugging: print out stems of a glyph */
  1469. static void
  1470. debugstems(
  1471.        char *name,
  1472.        STEM * hstems,
  1473.        int nhs,
  1474.        STEM * vstems,
  1475.        int nvs
  1476. )
  1477. {
  1478.     int             i;
  1479.  
  1480.     fprintf(pfa_file, "%% %s\n", name);
  1481.     fprintf(pfa_file, "%% %d horizontal stems:\n", nhs);
  1482.     for (i = 0; i < nhs; i++)
  1483.         fprintf(pfa_file, "%% %3d    %d (%d...%d) %c %c%c%c%c\n", i, hstems[i].value,
  1484.             hstems[i].from, hstems[i].to,
  1485.             ((hstems[i].flags & ST_UP) ? 'U' : 'D'),
  1486.             ((hstems[i].flags & ST_END) ? 'E' : '-'),
  1487.             ((hstems[i].flags & ST_FLAT) ? 'F' : '-'),
  1488.             ((hstems[i].flags & ST_ZONE) ? 'Z' : ' '),
  1489.             ((hstems[i].flags & ST_TOPZONE) ? 'T' : ' '));
  1490.     fprintf(pfa_file, "%% %d vertical stems:\n", nvs);
  1491.     for (i = 0; i < nvs; i++)
  1492.         fprintf(pfa_file, "%% %3d    %d (%d...%d) %c %c%c\n", i, vstems[i].value,
  1493.             vstems[i].from, vstems[i].to,
  1494.             ((vstems[i].flags & ST_UP) ? 'U' : 'D'),
  1495.             ((vstems[i].flags & ST_END) ? 'E' : '-'),
  1496.             ((vstems[i].flags & ST_FLAT) ? 'F' : '-'));
  1497. }
  1498.  
  1499. /* add pseudo-stems for the limits of the Blue zones to the stem array */
  1500. static int
  1501. addbluestems(
  1502.     STEM *s,
  1503.     int n
  1504. )
  1505. {
  1506.     int i;
  1507.  
  1508.     for(i=0; i<nblues && i<2; i+=2) { /* baseline */
  1509.         s[n].value=bluevalues[i];
  1510.         s[n].flags=ST_UP|ST_ZONE;
  1511.         /* don't overlap with anything */
  1512.         s[n].origin=s[n].from=s[n].to= -10000+i;
  1513.         n++;
  1514.         s[n].value=bluevalues[i+1];
  1515.         s[n].flags=ST_ZONE;
  1516.         /* don't overlap with anything */
  1517.         s[n].origin=s[n].from=s[n].to= -10000+i+1;
  1518.         n++;
  1519.     }
  1520.     for(i=2; i<nblues; i+=2) { /* top zones */
  1521.         s[n].value=bluevalues[i];
  1522.         s[n].flags=ST_UP|ST_ZONE|ST_TOPZONE;
  1523.         /* don't overlap with anything */
  1524.         s[n].origin=s[n].from=s[n].to= -10000+i;
  1525.         n++;
  1526.         s[n].value=bluevalues[i+1];
  1527.         s[n].flags=ST_ZONE|ST_TOPZONE;
  1528.         /* don't overlap with anything */
  1529.         s[n].origin=s[n].from=s[n].to= -10000+i+1;
  1530.         n++;
  1531.     }
  1532.     for(i=0; i<notherb; i+=2) { /* bottom zones */
  1533.         s[n].value=otherblues[i];
  1534.         s[n].flags=ST_UP|ST_ZONE;
  1535.         /* don't overlap with anything */
  1536.         s[n].origin=s[n].from=s[n].to= -10000+i+nblues;
  1537.         n++;
  1538.         s[n].value=otherblues[i+1];
  1539.         s[n].flags=ST_ZONE;
  1540.         /* don't overlap with anything */
  1541.         s[n].origin=s[n].from=s[n].to= -10000+i+1+nblues;
  1542.         n++;
  1543.     }
  1544.     return n;
  1545. }
  1546.  
  1547. /* sort stems in array */
  1548. static void
  1549. sortstems(
  1550.       STEM * s,
  1551.       int n
  1552. )
  1553. {
  1554.     int             i, j;
  1555.     STEM            x;
  1556.  
  1557.  
  1558.     /* a simple sorting */
  1559.     /* hm, the ordering criteria are not quite simple :-) 
  1560.      * if the values are tied
  1561.      * ST_UP always goes under not ST_UP
  1562.      * ST_ZONE goes on the most outer side
  1563.      * ST_END goes towards inner side after ST_ZONE
  1564.      * ST_FLAT goes on the inner side
  1565.      */
  1566.  
  1567.     for (i = 0; i < n; i++)
  1568.         for (j = i + 1; j < n; j++) {
  1569.             if(s[i].value < s[j].value)
  1570.                 continue;
  1571.             if(s[i].value == s[j].value) {
  1572.                 if( (s[i].flags & ST_UP) < (s[j].flags & ST_UP) )
  1573.                     continue;
  1574.                 if( (s[i].flags & ST_UP) == (s[j].flags & ST_UP) ) {
  1575.                     if( s[i].flags & ST_UP ) {
  1576.                         if(
  1577.                         (s[i].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
  1578.                             >
  1579.                         (s[j].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
  1580.                         )
  1581.                             continue;
  1582.                     } else {
  1583.                         if(
  1584.                         (s[i].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
  1585.                             <
  1586.                         (s[j].flags & (ST_ZONE|ST_FLAT|ST_END) ^ ST_FLAT)
  1587.                         )
  1588.                             continue;
  1589.                     }
  1590.                 }
  1591.             }
  1592.             x = s[j];
  1593.             s[j] = s[i];
  1594.             s[i] = x;
  1595.         }
  1596. }
  1597.  
  1598. /* check whether two stem borders overlap */
  1599.  
  1600. static int
  1601. stemoverlap(
  1602.         STEM * s1,
  1603.         STEM * s2
  1604. )
  1605. {
  1606.     int             result;
  1607.  
  1608.     if (s1->from <= s2->from && s1->to >= s2->from
  1609.         || s2->from <= s1->from && s2->to >= s1->from)
  1610.         result = 1;
  1611.     else
  1612.         result = 0;
  1613.  
  1614.     if (ISDBG(STEMOVERLAP))
  1615.         fprintf(pfa_file, "%% overlap %d(%d..%d)x%d(%d..%d)=%d\n",
  1616.             s1->value, s1->from, s1->to, s2->value, s2->from, s2->to, result);
  1617.     return result;
  1618. }
  1619.  
  1620. /* 
  1621.  * check if the stem [border] is in an appropriate blue zone
  1622.  * (currently not used)
  1623.  */
  1624.  
  1625. static int
  1626. steminblue(
  1627.     STEM *s
  1628. )
  1629. {
  1630.     int i, val;
  1631.  
  1632.     val=s->value;
  1633.     if(s->flags & ST_UP) {
  1634.         /* painted size up, look at lower zones */
  1635.         if(nblues>=2 && val>=bluevalues[0] && val<=bluevalues[1] )
  1636.             return 1;
  1637.         for(i=0; i<notherb; i++) {
  1638.             if( val>=otherblues[i] && val<=otherblues[i+1] )
  1639.                 return 1;
  1640.         }
  1641.     } else {
  1642.         /* painted side down, look at upper zones */
  1643.         for(i=2; i<nblues; i++) {
  1644.             if( val>=bluevalues[i] && val<=bluevalues[i+1] )
  1645.                 return 1;
  1646.         }
  1647.     }
  1648.  
  1649.     return 0;
  1650. }
  1651.  
  1652. /* mark the outermost stem [borders] in the blue zones */
  1653.  
  1654. static void
  1655. markbluestems(
  1656.     STEM *s,
  1657.     int nold
  1658. )
  1659. {
  1660.     int i, j, a, b, c;
  1661.     /*
  1662.      * traverse the list of Blue Values, mark the lowest upper
  1663.      * stem in each bottom zone and the topmost lower stem in
  1664.      * each top zone with ST_BLUE
  1665.      */
  1666.  
  1667.     /* top zones */
  1668.     for(i=2; i<nblues; i+=2) {
  1669.         a=bluevalues[i]; b=bluevalues[i+1];
  1670.         if(ISDBG(BLUESTEMS))
  1671.             fprintf(pfa_file, "%% looking at blue zone %d...%d\n", a, b);
  1672.         for(j=nold-1; j>=0; j--) {
  1673.             if( s[j].flags & (ST_ZONE|ST_UP|ST_END) )
  1674.                 continue;
  1675.             c=s[j].value;
  1676.             if(c<a) /* too low */
  1677.                 break;
  1678.             if(c<=b) { /* found the topmost stem border */
  1679.                 /* mark all the stems with the same value */
  1680.                 if(ISDBG(BLUESTEMS))
  1681.                     fprintf(pfa_file, "%% found D BLUE at %d\n", s[j].value);
  1682.                 /* include ST_END values */
  1683.                 while( s[j+1].value==c && (s[j+1].flags & ST_ZONE)==0 )
  1684.                     j++;
  1685.                 s[j].flags |= ST_BLUE;
  1686.                 for(j--; j>=0 && s[j].value==c 
  1687.                         && (s[j].flags & (ST_UP|ST_ZONE))==0 ; j--)
  1688.                     s[j].flags |= ST_BLUE;
  1689.                 break;
  1690.             }
  1691.         }
  1692.     }
  1693.     /* baseline */
  1694.     if(nblues>=2) {
  1695.         a=bluevalues[0]; b=bluevalues[1];
  1696.         for(j=0; j<nold; j++) {
  1697.             if( (s[j].flags & (ST_ZONE|ST_UP|ST_END))!=ST_UP )
  1698.                 continue;
  1699.             c=s[j].value;
  1700.             if(c>b) /* too high */
  1701.                 break;
  1702.             if(c>=a) { /* found the lowest stem border */
  1703.                 /* mark all the stems with the same value */
  1704.                 if(ISDBG(BLUESTEMS))
  1705.                     fprintf(pfa_file, "%% found U BLUE at %d\n", s[j].value);
  1706.                 /* include ST_END values */
  1707.                 while( s[j-1].value==c && (s[j-1].flags & ST_ZONE)==0 )
  1708.                     j--;
  1709.                 s[j].flags |= ST_BLUE;
  1710.                 for(j++; j<nold && s[j].value==c
  1711.                         && (s[j].flags & (ST_UP|ST_ZONE))==ST_UP ; j++)
  1712.                     s[j].flags |= ST_BLUE;
  1713.                 break;
  1714.             }
  1715.         }
  1716.     }
  1717.     /* bottom zones: the logic is the same as for baseline */
  1718.     for(i=0; i<notherb; i+=2) {
  1719.         a=otherblues[i]; b=otherblues[i+1];
  1720.         for(j=0; j<nold; j++) {
  1721.             if( (s[j].flags & (ST_UP|ST_ZONE|ST_END))!=ST_UP )
  1722.                 continue;
  1723.             c=s[j].value;
  1724.             if(c>b) /* too high */
  1725.                 break;
  1726.             if(c>=a) { /* found the lowest stem border */
  1727.                 /* mark all the stems with the same value */
  1728.                 if(ISDBG(BLUESTEMS))
  1729.                     fprintf(pfa_file, "%% found U BLUE at %d\n", s[j].value);
  1730.                 /* include ST_END values */
  1731.                 while( s[j-1].value==c && (s[j-1].flags & ST_ZONE)==0 )
  1732.                     j--;
  1733.                 s[j].flags |= ST_BLUE;
  1734.                 for(j++; j<nold && s[j].value==c
  1735.                         && (s[j].flags & (ST_UP|ST_ZONE))==ST_UP ; j++)
  1736.                     s[j].flags |= ST_BLUE;
  1737.                 break;
  1738.             }
  1739.         }
  1740.     }
  1741. }
  1742.  
  1743. /* Eliminate invalid stems, join equivalent lines and remove nested stems
  1744.  * to build the main (non-substituted) set of stems.
  1745.  * XXX add consideration of the italic angle
  1746.  */
  1747. static int
  1748. joinmainstems(
  1749.       STEM * s,
  1750.       int nold,
  1751.       int useblues /* do we use the blue values ? */
  1752. )
  1753. {
  1754. #define MAX_STACK    1000
  1755.     STEM            stack[MAX_STACK];
  1756.     int             nstack = 0;
  1757.     int             sbottom = 0;
  1758.     int             nnew;
  1759.     int             i, j, k;
  1760.     int             a, b, c, w1, w2, w3;
  1761.     int             fw, fd;
  1762.     /*
  1763.      * priority of the last found stem: 
  1764.      * 0 - nothing found yet 
  1765.      * 1 - has ST_END in it (one or more) 
  1766.      * 2 - has no ST_END and no ST_FLAT, can override only one stem 
  1767.      *     with priority 1 
  1768.      * 3 - has no ST_END and at least one ST_FLAT, can override one 
  1769.      *     stem with priority 2 or any number of stems with priority 1
  1770.      * 4 (handled separately) - has ST_BLUE, can override anything
  1771.      */
  1772.     int             readystem = 0;
  1773.     int             pri;
  1774.     int             nlps = 0;    /* number of non-committed
  1775.                      * lowest-priority stems */
  1776.  
  1777.  
  1778.     for (i = 0, nnew = 0; i < nold; i++) {
  1779.         if (s[i].flags & (ST_UP|ST_ZONE)) {
  1780.             if(s[i].flags & ST_BLUE) {
  1781.                 /* we just HAVE to use this value */
  1782.                 if (readystem)
  1783.                     nnew += 2;
  1784.                 readystem=0;
  1785.  
  1786.                 /* remember the list of Blue zone stems with the same value */
  1787.                 for(a=i, i++; i<nold && s[a].value==s[i].value
  1788.                     && (s[i].flags & ST_BLUE); i++)
  1789.                     {}
  1790.                 b=i; /* our range is a <= i < b */
  1791.                 c= -1; /* index of our best guess up to now */
  1792.                 pri=0;
  1793.                 /* try to find a match, don't cross blue zones */
  1794.                 for(; i<nold && (s[i].flags & ST_BLUE)==0; i++) {
  1795.                     if(s[i].flags & ST_UP) {
  1796.                         if(s[i].flags & ST_TOPZONE)
  1797.                             break;
  1798.                         else
  1799.                             continue;
  1800.                     }
  1801.                     for(j=a; j<b; j++) {
  1802.                         if(!stemoverlap(&s[j], &s[i]) )
  1803.                             continue;
  1804.                         /* consider priorities */
  1805.                         if( ( (s[j].flags|s[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) {
  1806.                             c=i;
  1807.                             goto bluematch;
  1808.                         }
  1809.                         if( ((s[j].flags|s[i].flags) & ST_END)==0 )  {
  1810.                             if(pri < 2) {
  1811.                                 c=i; pri=2;
  1812.                             }
  1813.                         } else {
  1814.                             if(pri == 0) {
  1815.                                 c=i; pri=1;
  1816.                             }
  1817.                         }
  1818.                     }
  1819.                 }
  1820.             bluematch:
  1821.                 /* clean up the stack */
  1822.                 nstack=sbottom=0;
  1823.                 readystem=0;
  1824.                 /* add this stem */
  1825.                 s[nnew++]=s[a];
  1826.                 if(c<0) { /* make one-dot-wide stem */
  1827.                     if(nnew>=b) { /* have no free space */
  1828.                         for(j=nold; j>=b; j--) /* make free space */
  1829.                             s[j]=s[j-1];
  1830.                         b++;
  1831.                         nold++;
  1832.                     }
  1833.                     s[nnew]=s[a];
  1834.                     s[nnew].flags &= ~(ST_UP|ST_BLUE);
  1835.                     nnew++;
  1836.                     i=b-1;
  1837.                 } else {
  1838.                     s[nnew++]=s[c];
  1839.                     i=c; /* skip up to this point */
  1840.                 }
  1841.                 if (ISDBG(MAINSTEMS))
  1842.                     fprintf(pfa_file, "%% +stem %d...%d U BLUE\n",
  1843.                         s[nnew-2].value, s[nnew-1].value);
  1844.             } else {
  1845.                 if (nstack >= MAX_STACK) {
  1846.                     WARNING_1 fprintf(stderr, "Warning: **** converter's stem stack overflow ****\n");
  1847.                     nstack = 0;
  1848.                 }
  1849.                 stack[nstack++] = s[i];
  1850.             }
  1851.         } else if(s[i].flags & ST_BLUE) {
  1852.             /* again, we just HAVE to use this value */
  1853.             if (readystem)
  1854.                 nnew += 2;
  1855.             readystem=0;
  1856.  
  1857.             /* remember the list of Blue zone stems with the same value */
  1858.             for(a=i, i++; i<nold && s[a].value==s[i].value
  1859.                 && (s[i].flags & ST_BLUE); i++)
  1860.                 {}
  1861.             b=i; /* our range is a <= i < b */
  1862.             c= -1; /* index of our best guess up to now */
  1863.             pri=0;
  1864.             /* try to find a match */
  1865.             for (i = nstack - 1; i >= 0; i--) {
  1866.                 if( (stack[i].flags & ST_UP)==0 ) {
  1867.                     if( (stack[i].flags & (ST_ZONE|ST_TOPZONE))==ST_ZONE )
  1868.                         break;
  1869.                     else
  1870.                         continue;
  1871.                 }
  1872.                 for(j=a; j<b; j++) {
  1873.                     if(!stemoverlap(&s[j], &stack[i]) )
  1874.                         continue;
  1875.                     /* consider priorities */
  1876.                     if( ( (s[j].flags|stack[i].flags) & (ST_FLAT|ST_END) )==ST_FLAT ) {
  1877.                         c=i;
  1878.                         goto bluedownmatch;
  1879.                     }
  1880.                     if( ((s[j].flags|stack[i].flags) & ST_END)==0 )  {
  1881.                         if(pri < 2) {
  1882.                             c=i; pri=2;
  1883.                         }
  1884.                     } else {
  1885.                         if(pri == 0) {
  1886.                             c=i; pri=1;
  1887.                         }
  1888.                     }
  1889.                 }
  1890.             }
  1891.         bluedownmatch:
  1892.             /* if found no match make a one-dot-wide stem */
  1893.             if(c<0) {
  1894.                 c=0;
  1895.                 stack[0]=s[b-1];
  1896.                 stack[0].flags |= ST_UP;
  1897.                 stack[0].flags &= ~ST_BLUE;
  1898.             }
  1899.             /* remove all the stems conflicting with this one */
  1900.             readystem=0;
  1901.             for(j=nnew-2; j>=0; j-=2) {
  1902.                 if (ISDBG(MAINSTEMS))
  1903.                     fprintf(pfa_file, "%% ?stem %d...%d -- %d\n",
  1904.                         s[j].value, s[j+1].value, stack[c].value);
  1905.                 if(s[j+1].value < stack[c].value) /* no conflict */
  1906.                     break;
  1907.                 if(s[j].flags & ST_BLUE) {
  1908.                     /* oops, we don't want to spoil other blue zones */
  1909.                     stack[c].value=s[j+1].value+1;
  1910.                     break;
  1911.                 }
  1912.                 if( (s[j].flags|s[j+1].flags) & ST_END ) {
  1913.                     if (ISDBG(MAINSTEMS))
  1914.                         fprintf(pfa_file, "%% -stem %d...%d p=1\n",
  1915.                             s[j].value, s[j+1].value);
  1916.                     continue; /* pri==1, silently discard it */
  1917.                 }
  1918.                 /* we want to discard no nore than 2 stems of pri>=2 */
  1919.                 if( ++readystem > 2 ) {
  1920.                     /* change our stem to not conflict */
  1921.                     stack[c].value=s[j+1].value+1;
  1922.                     break;
  1923.                 } else {
  1924.                     if (ISDBG(MAINSTEMS))
  1925.                         fprintf(pfa_file, "%% -stem %d...%d p>=2\n",
  1926.                             s[j].value, s[j+1].value);
  1927.                     continue;
  1928.                 }
  1929.             }
  1930.             nnew=j+2;
  1931.             /* add this stem */
  1932.             if(nnew>=b-1) { /* have no free space */
  1933.                 for(j=nold; j>=b-1; j--) /* make free space */
  1934.                     s[j]=s[j-1];
  1935.                 b++;
  1936.                 nold++;
  1937.             }
  1938.             s[nnew++]=stack[c];
  1939.             s[nnew++]=s[b-1];
  1940.             /* clean up the stack */
  1941.             nstack=sbottom=0;
  1942.             readystem=0;
  1943.             /* set the next position to search */
  1944.             i=b-1;
  1945.             if (ISDBG(MAINSTEMS))
  1946.                 fprintf(pfa_file, "%% +stem %d...%d D BLUE\n",
  1947.                     s[nnew-2].value, s[nnew-1].value);
  1948.         } else if (nstack > 0) {
  1949.  
  1950.             /*
  1951.              * check whether our stem overlaps with anything in
  1952.              * stack
  1953.              */
  1954.             for (j = nstack - 1; j >= sbottom; j--) {
  1955.                 if (s[i].value <= stack[j].value)
  1956.                     break;
  1957.                 if (stack[j].flags & ST_ZONE)
  1958.                     continue;
  1959.  
  1960.                 if ((s[i].flags & ST_END)
  1961.                     || (stack[j].flags & ST_END))
  1962.                     pri = 1;
  1963.                 else if ((s[i].flags & ST_FLAT)
  1964.                      || (stack[j].flags & ST_FLAT))
  1965.                     pri = 3;
  1966.                 else
  1967.                     pri = 2;
  1968.  
  1969.                 if (pri < readystem && s[nnew + 1].value >= stack[j].value
  1970.                     || !stemoverlap(&stack[j], &s[i]))
  1971.                     continue;
  1972.  
  1973.                 if (readystem > 1 && s[nnew + 1].value < stack[j].value) {
  1974.                     nnew += 2;
  1975.                     readystem = 0;
  1976.                     nlps = 0;
  1977.                 }
  1978.                 /*
  1979.                  * width of the previous stem (if it's
  1980.                  * present)
  1981.                  */
  1982.                 w1 = s[nnew + 1].value - s[nnew].value;
  1983.  
  1984.                 /* width of this stem */
  1985.                 w2 = s[i].value - stack[j].value;
  1986.  
  1987.                 if (readystem == 0) {
  1988.                     /* nothing yet, just add a new stem */
  1989.                     s[nnew] = stack[j];
  1990.                     s[nnew + 1] = s[i];
  1991.                     readystem = pri;
  1992.                     if (pri == 1)
  1993.                         nlps = 1;
  1994.                     else if (pri == 2)
  1995.                         sbottom = j;
  1996.                     else {
  1997.                         sbottom = j + 1;
  1998.                         while (sbottom < nstack
  1999.                                && stack[sbottom].value <= stack[j].value)
  2000.                             sbottom++;
  2001.                     }
  2002.                     if (ISDBG(MAINSTEMS))
  2003.                         fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
  2004.                             stack[j].value, s[i].value, pri, nlps);
  2005.                 } else if (pri == 1) {
  2006.                     if (stack[j].value > s[nnew + 1].value) {
  2007.                         /*
  2008.                          * doesn't overlap with the
  2009.                          * previous one
  2010.                          */
  2011.                         nnew += 2;
  2012.                         nlps++;
  2013.                         s[nnew] = stack[j];
  2014.                         s[nnew + 1] = s[i];
  2015.                         if (ISDBG(MAINSTEMS))
  2016.                             fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
  2017.                                 stack[j].value, s[i].value, pri, nlps);
  2018.                     } else if (w2 < w1) {
  2019.                         /* is narrower */
  2020.                         s[nnew] = stack[j];
  2021.                         s[nnew + 1] = s[i];
  2022.                         if (ISDBG(MAINSTEMS))
  2023.                             fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d %d->%d\n",
  2024.                                 stack[j].value, s[i].value, pri, nlps, w1, w2);
  2025.                     }
  2026.                 } else if (pri == 2) {
  2027.                     if (readystem == 2) {
  2028.                         /* choose the narrower stem */
  2029.                         if (w1 > w2) {
  2030.                             s[nnew] = stack[j];
  2031.                             s[nnew + 1] = s[i];
  2032.                             sbottom = j;
  2033.                             if (ISDBG(MAINSTEMS))
  2034.                                 fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
  2035.                                     stack[j].value, s[i].value, pri, nlps);
  2036.                         }
  2037.                         /* else readystem==1 */
  2038.                     } else if (stack[j].value > s[nnew + 1].value) {
  2039.                         /*
  2040.                          * value doesn't overlap with
  2041.                          * the previous one
  2042.                          */
  2043.                         nnew += 2;
  2044.                         nlps = 0;
  2045.                         s[nnew] = stack[j];
  2046.                         s[nnew + 1] = s[i];
  2047.                         sbottom = j;
  2048.                         readystem = pri;
  2049.                         if (ISDBG(MAINSTEMS))
  2050.                             fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
  2051.                                 stack[j].value, s[i].value, pri, nlps);
  2052.                     } else if (nlps == 1
  2053.                            || stack[j].value > s[nnew - 1].value) {
  2054.                         /*
  2055.                          * we can replace the top
  2056.                          * stem
  2057.                          */
  2058.                         nlps = 0;
  2059.                         s[nnew] = stack[j];
  2060.                         s[nnew + 1] = s[i];
  2061.                         readystem = pri;
  2062.                         sbottom = j;
  2063.                         if (ISDBG(MAINSTEMS))
  2064.                             fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
  2065.                                 stack[j].value, s[i].value, pri, nlps);
  2066.                     }
  2067.                 } else if (readystem == 3) {    /* that means also
  2068.                                  * pri==3 */
  2069.                     /* choose the narrower stem */
  2070.                     if (w1 > w2) {
  2071.                         s[nnew] = stack[j];
  2072.                         s[nnew + 1] = s[i];
  2073.                         sbottom = j + 1;
  2074.                         while (sbottom < nstack
  2075.                                && stack[sbottom].value <= stack[j].value)
  2076.                             sbottom++;
  2077.                         if (ISDBG(MAINSTEMS))
  2078.                             fprintf(pfa_file, "%% /stem %d...%d p=%d n=%d\n",
  2079.                                 stack[j].value, s[i].value, pri, nlps);
  2080.                     }
  2081.                 } else if (pri == 3) {
  2082.                     /*
  2083.                      * we can replace as many stems as
  2084.                      * neccessary
  2085.                      */
  2086.                     nnew += 2;
  2087.                     while (nnew > 0 && s[nnew - 1].value >= stack[j].value) {
  2088.                         nnew -= 2;
  2089.                         if (ISDBG(MAINSTEMS))
  2090.                             fprintf(pfa_file, "%% -stem %d..%d\n",
  2091.                                 s[nnew].value, s[nnew + 1].value);
  2092.                     }
  2093.                     nlps = 0;
  2094.                     s[nnew] = stack[j];
  2095.                     s[nnew + 1] = s[i];
  2096.                     readystem = pri;
  2097.                     sbottom = j + 1;
  2098.                     while (sbottom < nstack
  2099.                            && stack[sbottom].value <= stack[j].value)
  2100.                         sbottom++;
  2101.                     if (ISDBG(MAINSTEMS))
  2102.                         fprintf(pfa_file, "%% +stem %d...%d p=%d n=%d\n",
  2103.                             stack[j].value, s[i].value, pri, nlps);
  2104.                 }
  2105.             }
  2106.         }
  2107.     }
  2108.     if (readystem)
  2109.         nnew += 2;
  2110.  
  2111.     /* change the 1-pixel-wide stems to 20-pixel-wide stems if possible 
  2112.      * the constant 20 is recommended in the Type1 manual 
  2113.      */
  2114.     if(useblues) {
  2115.         for(i=0; i<nnew; i+=2) {
  2116.             if(s[i].value != s[i+1].value)
  2117.                 continue;
  2118.             if( ((s[i].flags ^ s[i+1].flags) & ST_BLUE)==0 )
  2119.                 continue;
  2120.             if( s[i].flags & ST_BLUE ) {
  2121.                 if(nnew>i+2 && s[i+2].value<s[i].value+22)
  2122.                     s[i+1].value=s[i+2].value-2; /* compensate for fuzziness */
  2123.                 else
  2124.                     s[i+1].value+=20;
  2125.             } else {
  2126.                 if(i>0 && s[i-1].value>s[i].value-22)
  2127.                     s[i].value=s[i-1].value+2; /* compensate for fuzziness */
  2128.                 else
  2129.                     s[i].value-=20;
  2130.             }
  2131.         }
  2132.     }
  2133.     /* make sure that no stem it stretched between
  2134.      * a top zone and a bottom zone
  2135.      */
  2136.     if(useblues) {
  2137.         for(i=0; i<nnew; i+=2) {
  2138.             a=10000; /* lowest border of top zone crosing the stem */
  2139.             b= -10000; /* highest border of bottom zone crossing the stem */
  2140.  
  2141.             for(j=2; j<nblues; j++) {
  2142.                 c=bluevalues[j];
  2143.                 if( c>=s[i].value && c<=s[i+1].value && c<a )
  2144.                     a=c;
  2145.             }
  2146.             if(nblues>=2) {
  2147.                 c=bluevalues[1];
  2148.                 if( c>=s[i].value && c<=s[i+1].value && c>b )
  2149.                     b=c;
  2150.             }
  2151.             for(j=1; j<notherb; j++) {
  2152.                 c=otherblues[j];
  2153.                 if( c>=s[i].value && c<=s[i+1].value && c>b )
  2154.                     b=c;
  2155.             }
  2156.             if( a!=10000 && b!= -10000 ) { /* it is stretched */
  2157.                 /* split the stem into 2 ghost stems */
  2158.                 for(j=nnew+1; j>i+1; j--) /* make free space */
  2159.                     s[j]=s[j-2];
  2160.                 nnew+=2;
  2161.  
  2162.                 if(s[i].value+22 >= a)
  2163.                     s[i+1].value=a-2; /* leave space for fuzziness */
  2164.                 else
  2165.                     s[i+1].value=s[i].value+20;
  2166.  
  2167.                 if(s[i+3].value-22 <= b)
  2168.                     s[i+2].value=b+2; /* leave space for fuzziness */
  2169.                 else
  2170.                     s[i+2].value=s[i+3].value-20;
  2171.  
  2172.                 i+=2;
  2173.             }
  2174.         }
  2175.     }
  2176.     /* look for triple stems */
  2177.     for (i = 0; i < nnew; i += 2) {
  2178.         if (nnew - i >= 6) {
  2179.             a = s[i].value + s[i + 1].value;
  2180.             b = s[i + 2].value + s[i + 3].value;
  2181.             c = s[i + 4].value + s[i + 5].value;
  2182.  
  2183.             w1 = s[i + 1].value - s[i].value;
  2184.             w2 = s[i + 3].value - s[i + 2].value;
  2185.             w3 = s[i + 5].value - s[i + 4].value;
  2186.  
  2187.             fw = w3 - w1;    /* fuzz in width */
  2188.             fd = ((c - b) - (b - a));    /* fuzz in distance
  2189.                              * (doubled) */
  2190.  
  2191.             /* we are able to handle some fuzz */
  2192.             /*
  2193.              * it doesn't hurt if the declared stem is a bit
  2194.              * narrower than actual unless it's an edge in
  2195.              * a blue zone
  2196.              */
  2197.             if (abs(abs(fd) - abs(fw)) * 5 < w2
  2198.                 && abs(fw) * 20 < (w1 + w3)) {    /* width dirrerence <10% */
  2199.  
  2200.                 if(useblues) { /* check that we don't disturb any blue stems */
  2201.                     j=c; k=a;
  2202.                     if (fw > 0) {
  2203.                         if (fd > 0) {
  2204.                             if( s[i+5].flags & ST_BLUE )
  2205.                                 continue;
  2206.                             j -= fw;
  2207.                         } else {
  2208.                             if( s[i+4].flags & ST_BLUE )
  2209.                                 continue;
  2210.                             j += fw;
  2211.                         }
  2212.                     } else if(fw < 0) {
  2213.                         if (fd > 0) {
  2214.                             if( s[i+1].flags & ST_BLUE )
  2215.                                 continue;
  2216.                             k -= fw;
  2217.                         } else {
  2218.                             if( s[i].flags & ST_BLUE )
  2219.                                 continue;
  2220.                             k += fw;
  2221.                         }
  2222.                     }
  2223.                     pri = ((j - b) - (b - k));
  2224.  
  2225.                     if (pri > 0) {
  2226.                         if( s[i+2].flags & ST_BLUE )
  2227.                             continue;
  2228.                     } else if(pri < 0) {
  2229.                         if( s[i+3].flags & ST_BLUE )
  2230.                             continue;
  2231.                     }
  2232.                 }
  2233.  
  2234.                 /*
  2235.                  * first fix up the width of 1st and 3rd
  2236.                  * stems
  2237.                  */
  2238.                 if (fw > 0) {
  2239.                     if (fd > 0) {
  2240.                         s[i + 5].value -= fw;
  2241.                         c -= fw;
  2242.                     } else {
  2243.                         s[i + 4].value += fw;
  2244.                         c += fw;
  2245.                     }
  2246.                 } else {
  2247.                     if (fd > 0) {
  2248.                         s[i + 1].value -= fw;
  2249.                         a -= fw;
  2250.                     } else {
  2251.                         s[i].value += fw;
  2252.                         a += fw;
  2253.                     }
  2254.                 }
  2255.                 fd = ((c - b) - (b - a));
  2256.  
  2257.                 if (fd > 0) {
  2258.                     s[i + 2].value += abs(fd) / 2;
  2259.                 } else {
  2260.                     s[i + 3].value -= abs(fd) / 2;
  2261.                 }
  2262.  
  2263.                 s[i].flags |= ST_3;
  2264.                 i += 4;
  2265.             }
  2266.         }
  2267.     }
  2268.  
  2269.     return (nnew & ~1);    /* number of lines must be always even */
  2270. }
  2271.  
  2272. /*
  2273.  * these macros and function allow to set the base stem,
  2274.  * check that it's not empty and subtract another stem
  2275.  * from the base stem (possibly dividing it into multiple parts)
  2276.  */
  2277.  
  2278. /* pairs for pieces of the base stem */
  2279. static short xbstem[MAX_STEMS*2]; 
  2280. /* index of the last point */
  2281. static int xblast= -1; 
  2282.  
  2283. #define setbasestem(from, to) \
  2284.     (xbstem[0]=from, xbstem[1]=to, xblast=1)
  2285. #define isbaseempty()    (xblast<=0)
  2286.  
  2287. /* returns 1 if was overlapping, 0 otherwise */
  2288. static int
  2289. subfrombase(
  2290.     int from,
  2291.     int to
  2292. ) 
  2293. {
  2294.     int a, b;
  2295.     int i, j;
  2296.  
  2297.     if(isbaseempty())
  2298.         return 0;
  2299.  
  2300.     /* handle the simple case simply */
  2301.     if(from > xbstem[xblast] || to < xbstem[0])
  2302.         return 0;
  2303.  
  2304.     /* the binary search may be more efficient */
  2305.     /* but for now the linear search is OK */
  2306.     for(b=1; from > xbstem[b]; b+=2) {} /* result: from <= xbstem[b] */
  2307.     for(a=xblast-1; to < xbstem[a]; a-=2) {} /* result: to >= xbstem[a] */
  2308.  
  2309.     /* now the interesting examples are:
  2310.      * (it was hard for me to understand, so I looked at the examples)
  2311.      * 1
  2312.      *     a|-----|          |-----|b   |-----|     |-----|
  2313.      *              f|-----|t
  2314.      * 2
  2315.      *     a|-----|b         |-----|    |-----|     |-----|
  2316.      *      f|--|t
  2317.      * 3
  2318.      *     a|-----|b         |-----|    |-----|     |-----|
  2319.      *           f|-----|t
  2320.      * 4
  2321.      *      |-----|b        a|-----|    |-----|     |-----|
  2322.      *          f|------------|t
  2323.      * 5
  2324.      *      |-----|          |-----|b   |-----|    a|-----|
  2325.      *                   f|-----------------------------|t
  2326.      * 6
  2327.      *      |-----|b         |-----|    |-----|    a|-----|
  2328.      *   f|--------------------------------------------------|t
  2329.      * 7
  2330.      *      |-----|b         |-----|   a|-----|     |-----|
  2331.      *          f|--------------------------|t
  2332.      */
  2333.  
  2334.     if(a < b-1) /* hits a gap  - example 1 */
  2335.         return 0;
  2336.  
  2337.     /* now the subtraction itself */
  2338.  
  2339.     if(a==b-1 && from > xbstem[a] && to < xbstem[b]) {
  2340.         /* overlaps with only one subrange and splits it - example 2 */
  2341.         j=xblast; i=(xblast+=2);
  2342.         while(j>=b)
  2343.             xbstem[i--]=xbstem[j--];
  2344.         xbstem[b]=from-1;
  2345.         xbstem[b+1]=to+1;
  2346.         return 1;
  2347.     /* becomes
  2348.      * 2a
  2349.      *     a|b   ||          |-----|    |-----|     |-----|
  2350.      *      f|--|t
  2351.      */
  2352.     }
  2353.  
  2354.     if(xbstem[b-1] < from) {
  2355.         /* cuts the back of this subrange - examples 3, 4, 7 */
  2356.         xbstem[b] = from-1;
  2357.         b+=2;
  2358.     /* becomes
  2359.      * 3a
  2360.      *     a|----|           |-----|b   |-----|     |-----|
  2361.      *           f|-----|t
  2362.      * 4a
  2363.      *      |---|           a|-----|b   |-----|     |-----|
  2364.      *          f|------------|t
  2365.      * 7a
  2366.      *      |---|            |-----|b  a|-----|     |-----|
  2367.      *          f|--------------------------|t
  2368.      */
  2369.     }
  2370.  
  2371.     if(xbstem[a+1] > to) {
  2372.         /* cuts the front of this subrange - examples 4a, 5, 7a */
  2373.         xbstem[a] = to+1;
  2374.         a-=2;
  2375.     /* becomes
  2376.      * 4b
  2377.      *     a|---|              |---|b   |-----|     |-----|
  2378.      *          f|------------|t
  2379.      * 5b
  2380.      *      |-----|          |-----|b  a|-----|          ||
  2381.      *                   f|-----------------------------|t
  2382.      * 7b
  2383.      *      |---|           a|-----|b        ||     |-----|
  2384.      *          f|--------------------------|t
  2385.      */
  2386.     }
  2387.  
  2388.     if(a < b-1) /* now after modification it hits a gap - examples 3a, 4b */
  2389.         return 1; /* because we have removed something */
  2390.  
  2391.     /* now remove the subranges completely covered by the new stem */
  2392.     /* examples 5b, 6, 7b */
  2393.     i=b-1; j=a+2;
  2394.     /* positioned as:
  2395.      * 5b                    i                           j
  2396.      *      |-----|          |-----|b  a|-----|          ||
  2397.      *                   f|-----------------------------|t
  2398.      * 6    i                                             xblast  j
  2399.      *      |-----|b         |-----|    |-----|    a|-----|
  2400.      *   f|--------------------------------------------------|t
  2401.      * 7b                    i               j
  2402.      *      |---|           a|-----|b        ||     |-----|
  2403.      *          f|--------------------------|t
  2404.      */
  2405.     while(j <= xblast)
  2406.         xbstem[i++]=xbstem[j++];
  2407.     xblast=i-1;
  2408.     return 1;
  2409. }
  2410.  
  2411. /* for debugging */
  2412. static void
  2413. printbasestem(void)
  2414. {
  2415.     int i;
  2416.  
  2417.     printf("( ");
  2418.     for(i=0; i<xblast; i+=2)
  2419.         printf("%d-%d ", xbstem[i], xbstem[i+1]);
  2420.     printf(") %d\n", xblast);
  2421. }
  2422.  
  2423. /*
  2424.  * Join the stem borders to build the sets of substituted stems
  2425.  * XXX add consideration of the italic angle
  2426.  */
  2427. static void
  2428. joinsubstems(
  2429.       STEM * s,
  2430.       short *pairs,
  2431.       int nold,
  2432.       int useblues /* do we use the blue values ? */
  2433. )
  2434. {
  2435.     int i, j, x;
  2436.     static unsigned char mx[MAX_STEMS][MAX_STEMS];
  2437.  
  2438.     /* we do the substituted groups of stems first
  2439.      * and it looks like it's going to be REALLY SLOW 
  2440.      * AND PAINFUL but let's bother about it later
  2441.      */
  2442.  
  2443.     /* for the substituted stems we don't bother about [hv]stem3 -
  2444.      * anyway the X11R6 rasterizer does not bother about hstem3
  2445.      * at all and is able to handle only one global vstem3
  2446.      * per glyph 
  2447.      */
  2448.  
  2449.     /* clean the used part of matrix */
  2450.     for(i=0; i<nold; i++)
  2451.         for(j=0; j<nold; j++)
  2452.             mx[i][j]=0;
  2453.  
  2454.     /* build the matrix of stem pairs */
  2455.     for(i=0; i<nold; i++) {
  2456.         if( s[i].flags & ST_ZONE )
  2457.             continue;
  2458.         if(s[i].flags & ST_BLUE)
  2459.             mx[i][i]=1; /* allow to pair with itself if no better pair */
  2460.         if(s[i].flags & ST_UP) { /* the down-stems are already matched */
  2461.             setbasestem(s[i].from, s[i].to);
  2462.             for(j=i+1; j<nold; j++) {
  2463.                 if(s[i].value==s[j].value
  2464.                 || s[j].flags & ST_ZONE ) {
  2465.                     continue;
  2466.                 }
  2467.                 x=subfrombase(s[j].from, s[j].to);
  2468.  
  2469.                 if(s[j].flags & ST_UP) /* match only up+down pairs */
  2470.                     continue;
  2471.  
  2472.                 mx[i][j]=mx[j][i]=x;
  2473.  
  2474.                 if(isbaseempty()) /* nothing else to do */
  2475.                     break;
  2476.             }
  2477.         }
  2478.     }
  2479.  
  2480.     if(ISDBG(SUBSTEMS)) {
  2481.         fprintf(pfa_file, "%%     ");
  2482.         for(j=0; j<nold; j++)
  2483.             putc( j%10==0 ? '0'+(j/10)%10 : ' ', pfa_file);
  2484.         fprintf(pfa_file, "\n%%     ");
  2485.         for(j=0; j<nold; j++)
  2486.             putc('0'+j%10, pfa_file);
  2487.         putc('\n', pfa_file);
  2488.         for(i=0; i<nold; i++) {
  2489.             fprintf(pfa_file, "%% %3d ",i);
  2490.             for(j=0; j<nold; j++)
  2491.                 putc( mx[i][j] ? 'X' : '.', pfa_file);
  2492.             putc('\n', pfa_file);
  2493.         }
  2494.     }
  2495.  
  2496.     /* now use the matrix to find the best pair for each stem */
  2497.     for(i=0; i<nold; i++) {
  2498.         int pri, lastpri, v, f;
  2499.  
  2500.         x= -1; /* best pair: none */
  2501.         lastpri=0;
  2502.  
  2503.         v=s[i].value;
  2504.         f=s[i].flags;
  2505.  
  2506.         if(f & ST_ZONE) {
  2507.             pairs[i]= -1;
  2508.             continue;
  2509.         }
  2510.  
  2511.         if(f & ST_UP) {
  2512.             for(j=i+1; j<nold; j++) {
  2513.                 if(mx[i][j]==0)
  2514.                     continue;
  2515.  
  2516.                 if( (f | s[j].flags) & ST_END )
  2517.                     pri=1;
  2518.                 else if( (f | s[j].flags) & ST_FLAT )
  2519.                     pri=3;
  2520.                 else
  2521.                     pri=2;
  2522.  
  2523.                 if(lastpri==0
  2524.                 || pri > lastpri  
  2525.                 && ( lastpri==1 || s[j].value-v<20 || (s[x].value-v)*2 >= s[j].value-v ) ) {
  2526.                     lastpri=pri;
  2527.                     x=j;
  2528.                 }
  2529.             }
  2530.         } else {
  2531.             for(j=i-1; j>=0; j--) {
  2532.                 if(mx[i][j]==0)
  2533.                     continue;
  2534.  
  2535.                 if( (f | s[j].flags) & ST_END )
  2536.                     pri=1;
  2537.                 else if( (f | s[j].flags) & ST_FLAT )
  2538.                     pri=3;
  2539.                 else
  2540.                     pri=2;
  2541.  
  2542.                 if(lastpri==0
  2543.                 || pri > lastpri  
  2544.                 && ( lastpri==1 || v-s[j].value<20 || (v-s[x].value)*2 >= v-s[j].value ) ) {
  2545.                     lastpri=pri;
  2546.                     x=j;
  2547.                 }
  2548.             }
  2549.         }
  2550.         if(x== -1 && mx[i][i])
  2551.             pairs[i]=i; /* a special case */
  2552.         else
  2553.             pairs[i]=x;
  2554.     }
  2555.  
  2556.     if(ISDBG(SUBSTEMS)) {
  2557.         for(i=0; i<nold; i++) {
  2558.             j=pairs[i];
  2559.             if(j>0)
  2560.                 fprintf(pfa_file, "%% %d...%d  (%d x %d)\n", s[i].value, s[j].value, i, j);
  2561.         }
  2562.     }
  2563. }
  2564.  
  2565. /*
  2566.  * Make all the stems originating at the same value get the
  2567.  * same width. Without this the rasterizer may move the dots
  2568.  * randomly up or down by one pixel, and that looks bad.
  2569.  * The prioritisation is the same as in findstemat().
  2570.  */
  2571. static void
  2572. uniformstems(
  2573.       STEM * s,
  2574.       short *pairs,
  2575.       int ns
  2576. )
  2577. {
  2578.     int i, j, from, to, val, dir;
  2579.     int pri, prevpri[2], wd, prevwd[2], prevbest[2];
  2580.  
  2581.     for(from=0; from<ns; from=to) {
  2582.         prevpri[0] = prevpri[1] = 0;
  2583.         prevwd[0] = prevwd[1] = 0;
  2584.         prevbest[0] = prevbest[1] = -1;
  2585.         val = s[from].value;
  2586.  
  2587.         for(to = from; to<ns && s[to].value == val; to++) {
  2588.             dir = ((s[to].flags & ST_UP)!=0);
  2589.  
  2590.             i=pairs[to]; /* the other side of this stem */
  2591.             if(i<0 || i==to)
  2592.                 continue; /* oops, no other side */
  2593.             wd=abs(s[i].value-val);
  2594.             if(wd == 0)
  2595.                 continue;
  2596.             pri=1;
  2597.             if( (s[to].flags | s[i].flags) & ST_END )
  2598.                 pri=0;
  2599.             if( prevbest[dir] == -1 || pri > prevpri[dir] || wd<prevwd[dir] ) {
  2600.                 prevbest[dir]=i;
  2601.                 prevpri[dir]=pri;
  2602.                 prevwd[dir]=wd;
  2603.             }
  2604.         }
  2605.  
  2606.         for(i=from; i<to; i++) {
  2607.             dir = ((s[i].flags & ST_UP)!=0);
  2608.             if(prevbest[dir] >= 0) {
  2609.                 if(ISDBG(SUBSTEMS)) {
  2610.                     fprintf(stderr, "at %d (%s %d) pair %d->%d(%d)\n", i, 
  2611.                         (dir ? "UP":"DOWN"), s[i].value, pairs[i], prevbest[dir],
  2612.                         s[prevbest[dir]].value);
  2613.                 }
  2614.                 pairs[i] = prevbest[dir];
  2615.             }
  2616.         }
  2617.     }
  2618. }
  2619.  
  2620. /* 
  2621.  * Find the best stem in the array at the specified (value, origin),
  2622.  * related to the entry ge.
  2623.  * Returns its index in the array sp, -1 means "none".
  2624.  * prevbest is the result for the other end of the line, we must 
  2625.  * find something better than it or leave it as it is.
  2626.  */
  2627. static int
  2628. findstemat(
  2629.     int value,
  2630.     int origin,
  2631.     GENTRY *ge,
  2632.     STEM *sp,
  2633.     short *pairs,
  2634.     int ns,
  2635.     int prevbest /* -1 means "none" */
  2636. )
  2637. {
  2638.     int i, min, max;
  2639.     int v, si;
  2640.     int pri, prevpri; /* priority, 0 = has ST_END, 1 = no ST_END */
  2641.     int wd, prevwd; /* stem width */
  2642.  
  2643.     si= -1; /* nothing yet */
  2644.  
  2645.     /* stems are ordered by value, binary search */
  2646.     min=0; max=ns; /* min <= i < max */
  2647.     while( min < max ) {
  2648.         i=(min+max)/2;
  2649.         v=sp[i].value;
  2650.         if(v<value)
  2651.             min=i+1;
  2652.         else if(v>value)
  2653.             max=i;
  2654.         else {
  2655.             si=i; /* temporary value */
  2656.             break;
  2657.         }
  2658.     }
  2659.  
  2660.     if( si < 0 ) /* found nothing this time */
  2661.         return prevbest;
  2662.  
  2663.     /* find the priority of the prevbest */
  2664.     /* we expect that prevbest has a pair */
  2665.     if(prevbest>=0) {
  2666.         i=pairs[prevbest];
  2667.         prevpri=1;
  2668.         if( (sp[prevbest].flags | sp[i].flags) & ST_END )
  2669.             prevpri=0; 
  2670.         prevwd=abs(sp[i].value-value);
  2671.     }
  2672.  
  2673.     /* stems are not ordered by origin, so now do the linear search */
  2674.  
  2675.     while( si>0 && sp[si-1].value==value ) /* find the first one */
  2676.         si--;
  2677.  
  2678.     for(; si<ns && sp[si].value==value; si++) {
  2679.         if(sp[si].origin != origin) 
  2680.             continue;
  2681.         if(sp[si].ge != ge) {
  2682.             if(ISDBG(SUBSTEMS)) {
  2683.                 fprintf(stderr, 
  2684.                     "dbg: possible self-intersection at v=%d o=%d exp_ge=0x%x ge=0x%x\n",
  2685.                     value, origin, ge, sp[si].ge);
  2686.             }
  2687.             continue;
  2688.         }
  2689.         i=pairs[si]; /* the other side of this stem */
  2690.         if(i<0)
  2691.             continue; /* oops, no other side */
  2692.         pri=1;
  2693.         if( (sp[si].flags | sp[i].flags) & ST_END )
  2694.             pri=0;
  2695.         wd=abs(sp[i].value-value);
  2696.         if( prevbest == -1 || pri >prevpri 
  2697.         || pri==prevpri && prevwd==0 || wd!=0 && wd<prevwd ) {
  2698.             prevbest=si;
  2699.             prevpri=pri;
  2700.             prevwd=wd;
  2701.             continue;
  2702.         }
  2703.     }
  2704.  
  2705.     return prevbest;
  2706. }
  2707.  
  2708. /* add the substems for one glyph entry 
  2709.  * (called from groupsubstems())
  2710.  * returns 0 if all OK, 1 if too many groups
  2711.  */
  2712.  
  2713. static int gssentry_lastgrp=0; /* reset to 0 for each new glyph */
  2714.  
  2715. static int
  2716. gssentry( /* crazy number of parameters */
  2717.     GENTRY *ge,
  2718.     STEM *hs, /* horizontal stems, sorted by value */
  2719.     short *hpairs,
  2720.     int nhs,
  2721.     STEM *vs, /* vertical stems, sorted by value */
  2722.     short *vpairs,
  2723.     int nvs,
  2724.     STEMBOUNDS *s,
  2725.     short *egp,
  2726.     int *nextvsi, 
  2727.     int *nexthsi /* -2 means "check by yourself" */
  2728. ) {
  2729.     enum {
  2730.         SI_VP,    /* vertical primary */
  2731.         SI_HP,    /* horizontal primary */
  2732.         SI_SIZE /* size of the array */
  2733.     };
  2734.     int si[SI_SIZE]; /* indexes of relevant stems */
  2735.  
  2736.     /* the bounds of the existing relevant stems */
  2737.     STEMBOUNDS r[ sizeof(si) / sizeof(si[0]) * 2 ];
  2738.     char rexpand; /* by how much we need to expand the group */
  2739.     int nr; /* and the number of them */
  2740.  
  2741.     /* yet more temporary storage */
  2742.     short lb, hb, isvert;
  2743.     int conflict, grp;
  2744.     int i, j, x, y;
  2745.  
  2746.  
  2747.     /* for each line or curve we try to find a horizontal and
  2748.      * a vertical stem corresponding to its first point
  2749.      * (corresponding to the last point of the previous
  2750.      * glyph entry), because the directions of the lines
  2751.      * will be eventually reversed and it will then become the last
  2752.      * point. And the T1 rasterizer applies the hints to 
  2753.      * the last point.
  2754.      *
  2755.      */
  2756.  
  2757.     /* start with the common part, the first point */
  2758.     x=ge->prev->ix3;
  2759.     y=ge->prev->iy3;
  2760.  
  2761.     if(*nextvsi == -2)
  2762.         si[SI_VP]=findstemat(x, y, ge, vs, vpairs, nvs, -1);
  2763.     else {
  2764.         si[SI_VP]= *nextvsi; *nextvsi= -2;
  2765.     }
  2766.     if(*nexthsi == -2)
  2767.         si[SI_HP]=findstemat(y, x, ge, hs, hpairs, nhs, -1);
  2768.     else {
  2769.         si[SI_HP]= *nexthsi; *nexthsi= -2;
  2770.     }
  2771.  
  2772.     /*
  2773.      * For the horizontal lines we make sure that both
  2774.      * ends of the line have the same horizontal stem,
  2775.      * and the same thing for vertical lines and stems.
  2776.      * In both cases we enforce the stem for the next entry.
  2777.      * Otherwise unpleasant effects may arise.
  2778.      */
  2779.  
  2780.     if(ge->type==GE_LINE) {
  2781.         if(ge->ix3==x) { /* vertical line */
  2782.             *nextvsi=si[SI_VP]=findstemat(x, ge->iy3, ge->frwd, vs, vpairs, nvs, si[SI_VP]);
  2783.         } else if(ge->iy3==y) { /* horizontal line */
  2784.             *nexthsi=si[SI_HP]=findstemat(y, ge->ix3, ge->frwd, hs, hpairs, nhs, si[SI_HP]);
  2785.         }
  2786.     }
  2787.  
  2788.     if(si[SI_VP]+si[SI_HP] == -2) /* no stems, leave it alone */
  2789.         return 0;
  2790.  
  2791.     /* build the array of relevant bounds */
  2792.     nr=0;
  2793.     for(i=0; i< sizeof(si) / sizeof(si[0]); i++) {
  2794.         STEM *sp;
  2795.         short *pairs;
  2796.         int step;
  2797.         int f;
  2798.         int nzones, firstzone, binzone, einzone;
  2799.         int btype, etype;
  2800.  
  2801.         if(si[i] < 0)
  2802.             continue;
  2803.  
  2804.         if(i<SI_HP) {
  2805.             r[nr].isvert=1; sp=vs; pairs=vpairs;
  2806.         } else {
  2807.             r[nr].isvert=0; sp=hs; pairs=hpairs;
  2808.         }
  2809.  
  2810.         r[nr].low=sp[ si[i] ].value;
  2811.         r[nr].high=sp[ pairs[ si[i] ] ].value;
  2812.  
  2813.         if(r[nr].low > r[nr].high) {
  2814.             j=r[nr].low; r[nr].low=r[nr].high; r[nr].high=j;
  2815.             step= -1;
  2816.         } else {
  2817.             step=1;
  2818.         }
  2819.  
  2820.         /* handle the interaction with Blue Zones */
  2821.  
  2822.         if(i>=SI_HP) { /* only for horizontal stems */
  2823.             if(si[i]==pairs[si[i]]) {
  2824.                 /* special case, the outermost stem in the
  2825.                  * Blue Zone without a pair, simulate it to 20-pixel
  2826.                  */
  2827.                 if(sp[ si[i] ].flags & ST_UP) {
  2828.                     r[nr].high+=20;
  2829.                     for(j=si[i]+1; j<nhs; j++)
  2830.                         if( (sp[j].flags & (ST_ZONE|ST_TOPZONE))
  2831.                         == (ST_ZONE|ST_TOPZONE) ) {
  2832.                             if(r[nr].high > sp[j].value-2)
  2833.                                 r[nr].high=sp[j].value-2;
  2834.                             break;
  2835.                         }
  2836.                 } else {
  2837.                     r[nr].low-=20;
  2838.                     for(j=si[i]-1; j>=0; j--)
  2839.                         if( (sp[j].flags & (ST_ZONE|ST_TOPZONE))
  2840.                         == (ST_ZONE) ) {
  2841.                             if(r[nr].low < sp[j].value+2)
  2842.                                 r[nr].low=sp[j].value+2;
  2843.                             break;
  2844.                         }
  2845.                 }
  2846.             }
  2847.  
  2848.             /* check that the stem borders don't end up in
  2849.              * different Blue Zones */
  2850.             f=sp[ si[i] ].flags;
  2851.             nzones=0; einzone=binzone=0;
  2852.             for(j=si[i]; j!=pairs[ si[i] ]; j+=step) {
  2853.                 if( (sp[j].flags & ST_ZONE)==0 )
  2854.                     continue;
  2855.                 /* if see a zone border going in the same direction */
  2856.                 if( ((f ^ sp[j].flags) & ST_UP)==0 ) {
  2857.                     if( ++nzones == 1 ) {
  2858.                         firstzone=sp[j].value; /* remember the first one */
  2859.                         etype=sp[j].flags & ST_TOPZONE;
  2860.                     }
  2861.                     einzone=1;
  2862.  
  2863.                 } else { /* the opposite direction */
  2864.                     if(nzones==0) { /* beginning is in a blue zone */
  2865.                         binzone=1;
  2866.                         btype=sp[j].flags & ST_TOPZONE;
  2867.                     }
  2868.                     einzone=0;
  2869.                 }
  2870.             }
  2871.  
  2872.             /* beginning and end are in Blue Zones of different types */
  2873.             if( binzone && einzone && (btype ^ etype)!=0 ) {
  2874.                 if( sp[si[i]].flags & ST_UP ) {
  2875.                     if(firstzone > r[nr].low+22)
  2876.                         r[nr].high=r[nr].low+20;
  2877.                     else
  2878.                         r[nr].high=firstzone-2;
  2879.                 } else {
  2880.                     if(firstzone < r[nr].high-22)
  2881.                         r[nr].low=r[nr].high-20;
  2882.                     else
  2883.                         r[nr].low=firstzone+2;
  2884.                 }
  2885.             }
  2886.         }
  2887.  
  2888.         if(ISDBG(SUBSTEMS))
  2889.             fprintf(pfa_file, "%%  at(%d,%d)[%d,%d] %d..%d %c (%d x %d)\n", x, y, i, nr,
  2890.                 r[nr].low, r[nr].high, r[nr].isvert ? 'v' : 'h',
  2891.                 si[i], pairs[si[i]]);
  2892.  
  2893.         nr++;
  2894.     }
  2895.  
  2896.     /* now try to find a group */
  2897.     conflict=0; /* no conflicts found yet */
  2898.     for(j=0; j<nr; j++)
  2899.         r[j].already=0;
  2900.  
  2901.     /* check if it fits into the last group */
  2902.     grp = gssentry_lastgrp;
  2903.     i = (grp==0)? 0 : egp[grp-1];
  2904.     for(; i<egp[grp]; i++) {
  2905.         lb=s[i].low; hb=s[i].high; isvert=s[i].isvert;
  2906.         for(j=0; j<nr; j++)
  2907.             if( r[j].isvert==isvert  /* intersects */
  2908.             && r[j].low <= hb && r[j].high >= lb ) {
  2909.                 if( r[j].low == lb && r[j].high == hb ) /* coincides */
  2910.                     r[j].already=1;
  2911.                 else
  2912.                     conflict=1;
  2913.             }
  2914.  
  2915.         if(conflict) 
  2916.             break;
  2917.     }
  2918.  
  2919.     if(conflict) { /* nope, check all the groups */
  2920.         for(j=0; j<nr; j++)
  2921.             r[j].already=0;
  2922.  
  2923.         for(i=0, grp=0; i<egp[NSTEMGRP-1]; i++) {
  2924.             if(i == egp[grp]) { /* checked all stems in a group */
  2925.                 if(conflict) {
  2926.                     grp++; conflict=0; /* check the next group */
  2927.                     for(j=0; j<nr; j++)
  2928.                         r[j].already=0;
  2929.                 } else
  2930.                     break; /* insert into this group */
  2931.             }
  2932.  
  2933.             lb=s[i].low; hb=s[i].high; isvert=s[i].isvert;
  2934.             for(j=0; j<nr; j++)
  2935.                 if( r[j].isvert==isvert  /* intersects */
  2936.                 && r[j].low <= hb && r[j].high >= lb ) {
  2937.                     if( r[j].low == lb && r[j].high == hb ) /* coincides */
  2938.                         r[j].already=1;
  2939.                     else
  2940.                         conflict=1;
  2941.                 }
  2942.  
  2943.             if(conflict) 
  2944.                 i=egp[grp]-1; /* fast forward to the next group */
  2945.         }
  2946.     }
  2947.  
  2948.     /* do we have any empty group ? */
  2949.     if(conflict && grp < NSTEMGRP-1) {
  2950.         grp++; conflict=0;
  2951.         for(j=0; j<nr; j++)
  2952.             r[j].already=0;
  2953.     }
  2954.  
  2955.     if(conflict) { /* oops, can't find any group to fit */
  2956.         return 1;
  2957.     }
  2958.  
  2959.     /* OK, add stems to this group */
  2960.  
  2961.     rexpand = nr;
  2962.     for(j=0; j<nr; j++)
  2963.         rexpand -= r[j].already;
  2964.  
  2965.     if(rexpand > 0) {
  2966.         for(i=egp[NSTEMGRP-1]-1; i>=egp[grp]; i--)
  2967.             s[i+rexpand]=s[i];
  2968.         for(i=0; i<nr; i++)
  2969.             if(!r[i].already)
  2970.                 s[egp[grp]++]=r[i];
  2971.         for(i=grp+1; i<NSTEMGRP; i++)
  2972.             egp[i]+=rexpand;
  2973.     }
  2974.  
  2975.     ge->stemid = gssentry_lastgrp = grp;
  2976.     return 0;
  2977. }
  2978.  
  2979. /*
  2980.  * Create the groups of substituted stems from the list.
  2981.  * Each group will be represented by a subroutine in the Subs
  2982.  * array.
  2983.  */
  2984.  
  2985. static void
  2986. groupsubstems(
  2987.     GLYPH *g,
  2988.     STEM *hs, /* horizontal stems, sorted by value */
  2989.     short *hpairs,
  2990.     int nhs,
  2991.     STEM *vs, /* vertical stems, sorted by value */
  2992.     short *vpairs,
  2993.     int nvs
  2994. )
  2995. {
  2996.     GENTRY *ge;
  2997.     int i, j;
  2998.  
  2999.     /* temporary storage */
  3000.     STEMBOUNDS s[MAX_STEMS*2];
  3001.     /* indexes in there, pointing past the end each stem group */
  3002.     short egp[NSTEMGRP]; 
  3003.  
  3004.     int nextvsi, nexthsi; /* -2 means "check by yourself" */
  3005.  
  3006.     for(i=0; i<NSTEMGRP; i++)
  3007.         egp[i]=0;
  3008.  
  3009.     nextvsi=nexthsi= -2; /* processed no horiz/vert line */
  3010.  
  3011.     gssentry_lastgrp = 0; /* reset the last group for new glyph */
  3012.  
  3013.     for (ge = g->entries; ge != 0; ge = ge->next) {
  3014.         if(ge->type!=GE_LINE && ge->type!=GE_CURVE) {
  3015.             nextvsi=nexthsi= -2; /* next path is independent */
  3016.             continue;
  3017.         }
  3018.  
  3019.         if( gssentry(ge, hs, hpairs, nhs, vs, vpairs, nvs, s, egp, &nextvsi, &nexthsi) ) {
  3020.             WARNING_2 fprintf(stderr, "*** glyph %s requires over %d hint subroutines, ignored them\n",
  3021.                 g->name, NSTEMGRP);
  3022.             /* it's better to have no substituted hints at all than have only part */
  3023.             for (ge = g->entries; ge != 0; ge = ge->next)
  3024.                 ge->stemid= -1;
  3025.             g->nsg=0; /* just to be safe, already is 0 by initialization */
  3026.             return;
  3027.         }
  3028.  
  3029.         /*
  3030.          * handle the last vert/horiz line of the path specially,
  3031.          * correct the hint for the first entry of the path
  3032.          */
  3033.         if(ge->frwd != ge->next && (nextvsi != -2 || nexthsi != -2) ) {
  3034.             if( gssentry(ge->frwd, hs, hpairs, nhs, vs, vpairs, nvs, s, egp, &nextvsi, &nexthsi) ) {
  3035.                 WARNING_2 fprintf(stderr, "*** glyph %s requires over %d hint subroutines, ignored them\n",
  3036.                     g->name, NSTEMGRP);
  3037.                 /* it's better to have no substituted hints at all than have only part */
  3038.                 for (ge = g->entries; ge != 0; ge = ge->next)
  3039.                     ge->stemid= -1;
  3040.                 g->nsg=0; /* just to be safe, already is 0 by initialization */
  3041.                 return;
  3042.             }
  3043.         }
  3044.  
  3045.     }
  3046.  
  3047.     /* find the index of the first empty group - same as the number of groups */
  3048.     if(egp[0]>0) {
  3049.         for(i=1; i<NSTEMGRP && egp[i]!=egp[i-1]; i++)
  3050.             {}
  3051.         g->nsg=i;
  3052.     } else
  3053.         g->nsg=0;
  3054.  
  3055.     if(ISDBG(SUBSTEMS)) {
  3056.         fprintf(pfa_file, "%% %d substem groups (%d %d %d)\n", g->nsg,
  3057.             g->nsg>1 ? egp[g->nsg-2] : -1,
  3058.             g->nsg>0 ? egp[g->nsg-1] : -1,
  3059.             g->nsg<NSTEMGRP ? egp[g->nsg] : -1 );
  3060.         j=0;
  3061.         for(i=0; i<g->nsg; i++) {
  3062.             fprintf(pfa_file, "%% grp %3d:      ", i);
  3063.             for(; j<egp[i]; j++) {
  3064.                 fprintf(pfa_file, " %4d...%-4d %c  ", s[j].low, s[j].high,
  3065.                     s[j].isvert ? 'v' : 'h');
  3066.             }
  3067.             fprintf(pfa_file, "\n");
  3068.         }
  3069.     }
  3070.  
  3071.     if(g->nsg==1) { /* it would be the same as the main stems */
  3072.         /* so erase it */
  3073.         for (ge = g->entries; ge != 0; ge = ge->next)
  3074.             ge->stemid= -1;
  3075.         g->nsg=0;
  3076.     }
  3077.  
  3078.     if(g->nsg>0) {
  3079.         if( (g->nsbs=malloc(g->nsg * sizeof (egp[0]))) == 0 ) {
  3080.             fprintf(stderr, "**** not enough memory for substituted hints ****\n");
  3081.             exit(255);
  3082.         }
  3083.         memmove(g->nsbs, egp, g->nsg * sizeof(short));
  3084.         if( (g->sbstems=malloc(egp[g->nsg-1] * sizeof (s[0]))) == 0 ) {
  3085.             fprintf(stderr, "**** not enough memory for substituted hints ****\n");
  3086.             exit(255);
  3087.         }
  3088.         memmove(g->sbstems, s, egp[g->nsg-1] * sizeof(s[0]));
  3089.     }
  3090. }
  3091.  
  3092. void
  3093. buildstems(
  3094.        GLYPH * g
  3095. )
  3096. {
  3097.     STEM            hs[MAX_STEMS], vs[MAX_STEMS];    /* temporary working
  3098.                              * storage */
  3099.     short    hs_pairs[MAX_STEMS], vs_pairs[MAX_STEMS]; /* best pairs for these stems */
  3100.     STEM           *sp;
  3101.     GENTRY         *ge, *nge, *pge;
  3102.     int             nx, ny;
  3103.     int ovalue;
  3104.     int totals, grp, lastgrp;
  3105.  
  3106.     assertisint(g, "buildstems int");
  3107.  
  3108.     g->nhs = g->nvs = 0;
  3109.     memset(hs, 0, sizeof hs);
  3110.     memset(vs, 0, sizeof vs);
  3111.  
  3112.     /* first search the whole character for possible stem points */
  3113.  
  3114.     for (ge = g->entries; ge != 0; ge = ge->next) {
  3115.         if (ge->type == GE_CURVE) {
  3116.  
  3117.             /*
  3118.              * SURPRISE! 
  3119.              * We consider the stems bound by the
  3120.              * H/V ends of the curves as flat ones.
  3121.              *
  3122.              * But we don't include the point on the
  3123.              * other end into the range.
  3124.              */
  3125.  
  3126.             /* first check the beginning of curve */
  3127.             /* if it is horizontal, add a hstem */
  3128.             if (ge->iy1 == ge->prev->iy3) {
  3129.                 hs[g->nhs].value = ge->iy1;
  3130.  
  3131.                 if (ge->ix1 < ge->prev->ix3)
  3132.                     hs[g->nhs].flags = ST_FLAT | ST_UP;
  3133.                 else
  3134.                     hs[g->nhs].flags = ST_FLAT;
  3135.  
  3136.                 hs[g->nhs].origin = ge->prev->ix3;
  3137.                 hs[g->nhs].ge = ge;
  3138.  
  3139.                 if (ge->ix1 < ge->prev->ix3) {
  3140.                     hs[g->nhs].from = ge->ix1+1;
  3141.                     hs[g->nhs].to = ge->prev->ix3;
  3142.                     if(hs[g->nhs].from > hs[g->nhs].to)
  3143.                         hs[g->nhs].from--;
  3144.                 } else {
  3145.                     hs[g->nhs].from = ge->prev->ix3;
  3146.                     hs[g->nhs].to = ge->ix1-1;
  3147.                     if(hs[g->nhs].from > hs[g->nhs].to)
  3148.                         hs[g->nhs].to++;
  3149.                 }
  3150.                 if (ge->ix1 != ge->prev->ix3)
  3151.                     g->nhs++;
  3152.             }
  3153.             /* if it is vertical, add a vstem */
  3154.             else if (ge->ix1 == ge->prev->ix3) {
  3155.                 vs[g->nvs].value = ge->ix1;
  3156.  
  3157.                 if (ge->iy1 > ge->prev->iy3)
  3158.                     vs[g->nvs].flags = ST_FLAT | ST_UP;
  3159.                 else
  3160.                     vs[g->nvs].flags = ST_FLAT;
  3161.  
  3162.                 vs[g->nvs].origin = ge->prev->iy3;
  3163.                 vs[g->nvs].ge = ge;
  3164.  
  3165.                 if (ge->iy1 < ge->prev->iy3) {
  3166.                     vs[g->nvs].from = ge->iy1+1;
  3167.                     vs[g->nvs].to = ge->prev->iy3;
  3168.                     if(vs[g->nvs].from > vs[g->nvs].to)
  3169.                         vs[g->nvs].from--;
  3170.                 } else {
  3171.                     vs[g->nvs].from = ge->prev->iy3;
  3172.                     vs[g->nvs].to = ge->iy1-1;
  3173.                     if(vs[g->nvs].from > vs[g->nvs].to)
  3174.                         vs[g->nvs].to++;
  3175.                 }
  3176.  
  3177.                 if (ge->iy1 != ge->prev->iy3)
  3178.                     g->nvs++;
  3179.             }
  3180.             /* then check the end of curve */
  3181.             /* if it is horizontal, add a hstem */
  3182.             if (ge->iy3 == ge->iy2) {
  3183.                 hs[g->nhs].value = ge->iy3;
  3184.  
  3185.                 if (ge->ix3 < ge->ix2)
  3186.                     hs[g->nhs].flags = ST_FLAT | ST_UP;
  3187.                 else
  3188.                     hs[g->nhs].flags = ST_FLAT;
  3189.  
  3190.                 hs[g->nhs].origin = ge->ix3;
  3191.                 hs[g->nhs].ge = ge->frwd;
  3192.  
  3193.                 if (ge->ix3 < ge->ix2) {
  3194.                     hs[g->nhs].from = ge->ix3;
  3195.                     hs[g->nhs].to = ge->ix2-1;
  3196.                     if( hs[g->nhs].from > hs[g->nhs].to )
  3197.                         hs[g->nhs].to++;
  3198.                 } else {
  3199.                     hs[g->nhs].from = ge->ix2+1;
  3200.                     hs[g->nhs].to = ge->ix3;
  3201.                     if( hs[g->nhs].from > hs[g->nhs].to )
  3202.                         hs[g->nhs].from--;
  3203.                 }
  3204.  
  3205.                 if (ge->ix3 != ge->ix2)
  3206.                     g->nhs++;
  3207.             }
  3208.             /* if it is vertical, add a vstem */
  3209.             else if (ge->ix3 == ge->ix2) {
  3210.                 vs[g->nvs].value = ge->ix3;
  3211.  
  3212.                 if (ge->iy3 > ge->iy2)
  3213.                     vs[g->nvs].flags = ST_FLAT | ST_UP;
  3214.                 else
  3215.                     vs[g->nvs].flags = ST_FLAT;
  3216.  
  3217.                 vs[g->nvs].origin = ge->iy3;
  3218.                 vs[g->nvs].ge = ge->frwd;
  3219.  
  3220.                 if (ge->iy3 < ge->iy2) {
  3221.                     vs[g->nvs].from = ge->iy3;
  3222.                     vs[g->nvs].to = ge->iy2-1;
  3223.                     if( vs[g->nvs].from > vs[g->nvs].to )
  3224.                         vs[g->nvs].to++;
  3225.                 } else {
  3226.                     vs[g->nvs].from = ge->iy2+1;
  3227.                     vs[g->nvs].to = ge->iy3;
  3228.                     if( vs[g->nvs].from > vs[g->nvs].to )
  3229.                         vs[g->nvs].from--;
  3230.                 }
  3231.  
  3232.                 if (ge->iy3 != ge->iy2)
  3233.                     g->nvs++;
  3234.             } else {
  3235.  
  3236.                 /*
  3237.                  * check the end of curve for a not smooth
  3238.                  * local extremum
  3239.                  */
  3240.                 nge = ge->frwd;
  3241.  
  3242.                 if (nge == 0)
  3243.                     continue;
  3244.                 else if (nge->type == GE_LINE) {
  3245.                     nx = nge->ix3;
  3246.                     ny = nge->iy3;
  3247.                 } else if (nge->type == GE_CURVE) {
  3248.                     nx = nge->ix1;
  3249.                     ny = nge->iy1;
  3250.                 } else
  3251.                     continue;
  3252.  
  3253.                 /* check for vertical extremums */
  3254.                 if (ge->iy3 > ge->iy2 && ge->iy3 > ny
  3255.                 || ge->iy3 < ge->iy2 && ge->iy3 < ny) {
  3256.                     hs[g->nhs].value = ge->iy3;
  3257.                     hs[g->nhs].from
  3258.                         = hs[g->nhs].to
  3259.                         = hs[g->nhs].origin = ge->ix3;
  3260.                     hs[g->nhs].ge = ge->frwd;
  3261.  
  3262.                     if (ge->ix3 < ge->ix2
  3263.                         || nx < ge->ix3)
  3264.                         hs[g->nhs].flags = ST_UP;
  3265.                     else
  3266.                         hs[g->nhs].flags = 0;
  3267.  
  3268.                     if (ge->ix3 != ge->ix2 || nx != ge->ix3)
  3269.                         g->nhs++;
  3270.                 }
  3271.                 /*
  3272.                  * the same point may be both horizontal and
  3273.                  * vertical extremum
  3274.                  */
  3275.                 /* check for horizontal extremums */
  3276.                 if (ge->ix3 > ge->ix2 && ge->ix3 > nx
  3277.                 || ge->ix3 < ge->ix2 && ge->ix3 < nx) {
  3278.                     vs[g->nvs].value = ge->ix3;
  3279.                     vs[g->nvs].from
  3280.                         = vs[g->nvs].to
  3281.                         = vs[g->nvs].origin = ge->iy3;
  3282.                     vs[g->nvs].ge = ge->frwd;
  3283.  
  3284.                     if (ge->iy3 > ge->iy2
  3285.                         || ny > ge->iy3)
  3286.                         vs[g->nvs].flags = ST_UP;
  3287.                     else
  3288.                         vs[g->nvs].flags = 0;
  3289.  
  3290.                     if (ge->iy3 != ge->iy2 || ny != ge->iy3)
  3291.                         g->nvs++;
  3292.                 }
  3293.             }
  3294.  
  3295.         } else if (ge->type == GE_LINE) {
  3296.             nge = ge->frwd;
  3297.  
  3298.             /* if it is horizontal, add a hstem */
  3299.             /* and the ends as vstems if they brace the line */
  3300.             if (ge->iy3 == ge->prev->iy3
  3301.             && ge->ix3 != ge->prev->ix3) {
  3302.                 hs[g->nhs].value = ge->iy3;
  3303.                 if (ge->ix3 < ge->prev->ix3) {
  3304.                     hs[g->nhs].flags = ST_FLAT | ST_UP;
  3305.                     hs[g->nhs].from = ge->ix3;
  3306.                     hs[g->nhs].to = ge->prev->ix3;
  3307.                 } else {
  3308.                     hs[g->nhs].flags = ST_FLAT;
  3309.                     hs[g->nhs].from = ge->prev->ix3;
  3310.                     hs[g->nhs].to = ge->ix3;
  3311.                 }
  3312.                 hs[g->nhs].origin = ge->ix3;
  3313.                 hs[g->nhs].ge = ge->frwd;
  3314.  
  3315.                 pge = ge->bkwd;
  3316.  
  3317.                 /* add beginning as vstem */
  3318.                 vs[g->nvs].value = pge->ix3;
  3319.                 vs[g->nvs].origin
  3320.                     = vs[g->nvs].from
  3321.                     = vs[g->nvs].to = pge->iy3;
  3322.                 vs[g->nvs].ge = ge;
  3323.  
  3324.                 if(pge->type==GE_CURVE)
  3325.                     ovalue=pge->iy2;
  3326.                 else
  3327.                     ovalue=pge->prev->iy3;
  3328.  
  3329.                 if (pge->iy3 > ovalue)
  3330.                     vs[g->nvs].flags = ST_UP | ST_END;
  3331.                 else if (pge->iy3 < ovalue)
  3332.                     vs[g->nvs].flags = ST_END;
  3333.                 else
  3334.                     vs[g->nvs].flags = 0;
  3335.  
  3336.                 if( vs[g->nvs].flags != 0 )
  3337.                     g->nvs++;
  3338.  
  3339.                 /* add end as vstem */
  3340.                 vs[g->nvs].value = ge->ix3;
  3341.                 vs[g->nvs].origin
  3342.                     = vs[g->nvs].from
  3343.                     = vs[g->nvs].to = ge->iy3;
  3344.                 vs[g->nvs].ge = ge->frwd;
  3345.  
  3346.                 if(nge->type==GE_CURVE)
  3347.                     ovalue=nge->iy1;
  3348.                 else
  3349.                     ovalue=nge->iy3;
  3350.  
  3351.                 if (ovalue > ge->iy3)
  3352.                     vs[g->nvs].flags = ST_UP | ST_END;
  3353.                 else if (ovalue < ge->iy3)
  3354.                     vs[g->nvs].flags = ST_END;
  3355.                 else
  3356.                     vs[g->nvs].flags = 0;
  3357.  
  3358.                 if( vs[g->nvs].flags != 0 )
  3359.                     g->nvs++;
  3360.  
  3361.                 g->nhs++;
  3362.             }
  3363.             /* if it is vertical, add a vstem */
  3364.             /* and the ends as hstems if they brace the line  */
  3365.             else if (ge->ix3 == ge->prev->ix3 
  3366.             && ge->iy3 != ge->prev->iy3) {
  3367.                 vs[g->nvs].value = ge->ix3;
  3368.                 if (ge->iy3 > ge->prev->iy3) {
  3369.                     vs[g->nvs].flags = ST_FLAT | ST_UP;
  3370.                     vs[g->nvs].from = ge->prev->iy3;
  3371.                     vs[g->nvs].to = ge->iy3;
  3372.                 } else {
  3373.                     vs[g->nvs].flags = ST_FLAT;
  3374.                     vs[g->nvs].from = ge->iy3;
  3375.                     vs[g->nvs].to = ge->prev->iy3;
  3376.                 }
  3377.                 vs[g->nvs].origin = ge->iy3;
  3378.                 vs[g->nvs].ge = ge->frwd;
  3379.  
  3380.                 pge = ge->bkwd;
  3381.  
  3382.                 /* add beginning as hstem */
  3383.                 hs[g->nhs].value = pge->iy3;
  3384.                 hs[g->nhs].origin
  3385.                     = hs[g->nhs].from
  3386.                     = hs[g->nhs].to = pge->ix3;
  3387.                 hs[g->nhs].ge = ge;
  3388.  
  3389.                 if(pge->type==GE_CURVE)
  3390.                     ovalue=pge->ix2;
  3391.                 else
  3392.                     ovalue=pge->prev->ix3;
  3393.  
  3394.                 if (pge->ix3 < ovalue)
  3395.                     hs[g->nhs].flags = ST_UP | ST_END;
  3396.                 else if (pge->ix3 > ovalue)
  3397.                     hs[g->nhs].flags = ST_END;
  3398.                 else
  3399.                     hs[g->nhs].flags = 0;
  3400.  
  3401.                 if( hs[g->nhs].flags != 0 )
  3402.                     g->nhs++;
  3403.  
  3404.                 /* add end as hstem */
  3405.                 hs[g->nhs].value = ge->iy3;
  3406.                 hs[g->nhs].origin
  3407.                     = hs[g->nhs].from
  3408.                     = hs[g->nhs].to = ge->ix3;
  3409.                 hs[g->nhs].ge = ge->frwd;
  3410.  
  3411.                 if(nge->type==GE_CURVE)
  3412.                     ovalue=nge->ix1;
  3413.                 else
  3414.                     ovalue=nge->ix3;
  3415.  
  3416.                 if (ovalue < ge->ix3)
  3417.                     hs[g->nhs].flags = ST_UP | ST_END;
  3418.                 else if (ovalue > ge->ix3)
  3419.                     hs[g->nhs].flags = ST_END;
  3420.                 else
  3421.                     hs[g->nhs].flags = 0;
  3422.  
  3423.                 if( hs[g->nhs].flags != 0 )
  3424.                     g->nhs++;
  3425.  
  3426.                 g->nvs++;
  3427.             }
  3428.             /*
  3429.              * check the end of line for a not smooth local
  3430.              * extremum
  3431.              */
  3432.             nge = ge->frwd;
  3433.  
  3434.             if (nge == 0)
  3435.                 continue;
  3436.             else if (nge->type == GE_LINE) {
  3437.                 nx = nge->ix3;
  3438.                 ny = nge->iy3;
  3439.             } else if (nge->type == GE_CURVE) {
  3440.                 nx = nge->ix1;
  3441.                 ny = nge->iy1;
  3442.             } else
  3443.                 continue;
  3444.  
  3445.             /* check for vertical extremums */
  3446.             if (ge->iy3 > ge->prev->iy3 && ge->iy3 > ny
  3447.             || ge->iy3 < ge->prev->iy3 && ge->iy3 < ny) {
  3448.                 hs[g->nhs].value = ge->iy3;
  3449.                 hs[g->nhs].from
  3450.                     = hs[g->nhs].to
  3451.                     = hs[g->nhs].origin = ge->ix3;
  3452.                 hs[g->nhs].ge = ge->frwd;
  3453.  
  3454.                 if (ge->ix3 < ge->prev->ix3
  3455.                     || nx < ge->ix3)
  3456.                     hs[g->nhs].flags = ST_UP;
  3457.                 else
  3458.                     hs[g->nhs].flags = 0;
  3459.  
  3460.                 if (ge->ix3 != ge->prev->ix3 || nx != ge->ix3)
  3461.                     g->nhs++;
  3462.             }
  3463.             /*
  3464.              * the same point may be both horizontal and vertical
  3465.              * extremum
  3466.              */
  3467.             /* check for horizontal extremums */
  3468.             if (ge->ix3 > ge->prev->ix3 && ge->ix3 > nx
  3469.             || ge->ix3 < ge->prev->ix3 && ge->ix3 < nx) {
  3470.                 vs[g->nvs].value = ge->ix3;
  3471.                 vs[g->nvs].from
  3472.                     = vs[g->nvs].to
  3473.                     = vs[g->nvs].origin = ge->iy3;
  3474.                 vs[g->nvs].ge = ge->frwd;
  3475.  
  3476.                 if (ge->iy3 > ge->prev->iy3
  3477.                     || ny > ge->iy3)
  3478.                     vs[g->nvs].flags = ST_UP;
  3479.                 else
  3480.                     vs[g->nvs].flags = 0;
  3481.  
  3482.                 if (ge->iy3 != ge->prev->iy3 || ny != ge->iy3)
  3483.                     g->nvs++;
  3484.             }
  3485.         }
  3486.     }
  3487.  
  3488.     g->nhs=addbluestems(hs, g->nhs);
  3489.     sortstems(hs, g->nhs);
  3490.     sortstems(vs, g->nvs);
  3491.  
  3492.     if (ISDBG(STEMS))
  3493.         debugstems(g->name, hs, g->nhs, vs, g->nvs);
  3494.  
  3495.     /* find the stems interacting with the Blue Zones */
  3496.     markbluestems(hs, g->nhs);
  3497.  
  3498.     if(subhints) {
  3499.         if (ISDBG(SUBSTEMS))
  3500.             fprintf(pfa_file, "%% %s: joining subst horizontal stems\n", g->name);
  3501.         joinsubstems(hs, hs_pairs, g->nhs, 1);
  3502.         uniformstems(hs, hs_pairs, g->nhs);
  3503.  
  3504.         if (ISDBG(SUBSTEMS))
  3505.             fprintf(pfa_file, "%% %s: joining subst vertical stems\n", g->name);
  3506.         joinsubstems(vs, vs_pairs, g->nvs, 0);
  3507.  
  3508.         groupsubstems(g, hs, hs_pairs, g->nhs, vs, vs_pairs, g->nvs);
  3509.     }
  3510.  
  3511.     if (ISDBG(MAINSTEMS))
  3512.         fprintf(pfa_file, "%% %s: joining main horizontal stems\n", g->name);
  3513.     g->nhs = joinmainstems(hs, g->nhs, 1);
  3514.     if (ISDBG(MAINSTEMS))
  3515.         fprintf(pfa_file, "%% %s: joining main vertical stems\n", g->name);
  3516.     g->nvs = joinmainstems(vs, g->nvs, 0);
  3517.  
  3518.     if (ISDBG(MAINSTEMS))
  3519.         debugstems(g->name, hs, g->nhs, vs, g->nvs);
  3520.  
  3521.     if(g->nhs > 0) {
  3522.         if ((sp = malloc(sizeof(STEM) * g->nhs)) == 0) {
  3523.             fprintf(stderr, "**** not enough memory for hints ****\n");
  3524.             exit(255);
  3525.         }
  3526.         g->hstems = sp;
  3527.         memcpy(sp, hs, sizeof(STEM) * g->nhs);
  3528.     } else
  3529.         g->hstems = 0;
  3530.  
  3531.     if(g->nvs > 0) {
  3532.         if ((sp = malloc(sizeof(STEM) * g->nvs)) == 0) {
  3533.             fprintf(stderr, "**** not enough memory for hints ****\n");
  3534.             exit(255);
  3535.         }
  3536.         g->vstems = sp;
  3537.         memcpy(sp, vs, sizeof(STEM) * g->nvs);
  3538.     } else
  3539.         g->vstems = 0;
  3540.  
  3541.     /* now check that the stems won't overflow the interpreter's stem stack:
  3542.      * some interpreters (like X11) push the stems on each change into
  3543.      * stack and pop them only after the whole glyphs is completed.
  3544.      */
  3545.  
  3546.     totals = (g->nhs+g->nvs) / 2; /* we count whole stems, not halves */
  3547.     lastgrp = -1;
  3548.  
  3549.     for (ge = g->entries; ge != 0; ge = ge->next) {
  3550.         grp=ge->stemid;
  3551.         if(grp >= 0 && grp != lastgrp)  {
  3552.             if(grp==0)
  3553.                 totals += g->nsbs[0];
  3554.             else
  3555.                 totals += g->nsbs[grp] - g->nsbs[grp-1];
  3556.  
  3557.             lastgrp = grp;
  3558.         }
  3559.     }
  3560.  
  3561.     /* be on the safe side, check for >= , not > */
  3562.     if(totals >= max_stemdepth) {  /* oops, too deep */
  3563.         WARNING_2 {
  3564.             fprintf(stderr, "Warning: glyph %s needs hint stack depth %d\n", g->name, totals);
  3565.             fprintf(stderr, "  (limit %d): removed the substituted hints from it\n", max_stemdepth);
  3566.         }
  3567.         if(g->nsg > 0) {
  3568.             for (ge = g->entries; ge != 0; ge = ge->next)
  3569.                 ge->stemid = -1;
  3570.             free(g->sbstems); g->sbstems = 0;
  3571.             free(g->nsbs); g->nsbs = 0;
  3572.             g->nsg = 0;
  3573.         }
  3574.     }
  3575.  
  3576.     /* now check if there are too many main stems */
  3577.     totals = (g->nhs+g->nvs) / 2; /* we count whole stems, not halves */
  3578.     if(totals >= max_stemdepth) { 
  3579.         /* even worse, too much of non-substituted stems */
  3580.         WARNING_2 {
  3581.             fprintf(stderr, "Warning: glyph %s has %d main hints\n", g->name, totals);
  3582.             fprintf(stderr, "  (limit %d): removed the hints from it\n", max_stemdepth);
  3583.         }
  3584.         if(g->vstems) {
  3585.             free(g->vstems); g->vstems = 0; g->nvs = 0;
  3586.         }
  3587.         if(g->hstems) {
  3588.             free(g->hstems); g->hstems = 0; g->nhs = 0;
  3589.         }
  3590.     }
  3591. }
  3592.  
  3593. /* convert weird curves that are close to lines into lines.
  3594. */
  3595.  
  3596. void
  3597. fstraighten(
  3598.        GLYPH * g
  3599. )
  3600. {
  3601.     GENTRY         *ge, *pge, *nge, *ige;
  3602.     double          df;
  3603.     int             dir;
  3604.     double          iln, oln;
  3605.     int             svdir, i, o;
  3606.  
  3607.     for (ige = g->entries; ige != 0; ige = ige->next) {
  3608.         if (ige->type != GE_CURVE)
  3609.             continue;
  3610.  
  3611.         ge = ige;
  3612.         pge = ge->bkwd;
  3613.         nge = ge->frwd;
  3614.  
  3615.         df = 0.;
  3616.  
  3617.         /* look for vertical then horizontal */
  3618.         for(i=0; i<2; i++) {
  3619.             o = !i; /* other axis */
  3620.  
  3621.             iln = fabs(ge->fpoints[i][2] - pge->fpoints[i][2]);
  3622.             oln = fabs(ge->fpoints[o][2] - pge->fpoints[o][2]);
  3623.             /*
  3624.              * if current curve is almost a vertical line, and it
  3625.              * doesn't begin or end horizontally (and the prev/next
  3626.              * line doesn't join smoothly ?)
  3627.              */
  3628.             if( oln < 1.
  3629.             || ge->fpoints[o][2] == ge->fpoints[o][1] 
  3630.             || ge->fpoints[o][0] == pge->fpoints[o][2]
  3631.             || iln > 2.
  3632.             || iln > 1.  && iln/oln > 0.1 )
  3633.                 continue;
  3634.  
  3635.  
  3636.             if(ISDBG(STRAIGHTEN)) 
  3637.                 fprintf(stderr,"** straighten almost %s\n", (i? "horizontal":"vertical"));
  3638.  
  3639.             df = ge->fpoints[i][2] - pge->fpoints[i][2];
  3640.             dir = fsign(ge->fpoints[o][2] - pge->fpoints[o][2]);
  3641.             ge->type = GE_LINE;
  3642.  
  3643.             /*
  3644.              * suck in all the sequence of such almost lines
  3645.              * going in the same direction but not deviating
  3646.              * too far from vertical
  3647.              */
  3648.             iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]);
  3649.             oln = nge->fpoints[o][2] - ge->fpoints[o][2];
  3650.  
  3651.             while (fabs(df) <= 5 && nge->type == GE_CURVE
  3652.             && dir == fsign(oln) /* that also gives oln != 0 */
  3653.             && iln <= 2.
  3654.             && ( iln <= 1.  || iln/fabs(oln) <= 0.1 ) ) {
  3655.                 ge->fx3 = nge->fx3;
  3656.                 ge->fy3 = nge->fy3;
  3657.  
  3658.                 if(ISDBG(STRAIGHTEN))
  3659.                     fprintf(stderr,"** straighten collapsing %s\n", (i? "horizontal":"vertical"));
  3660.                 freethisge(nge);
  3661.                 fixendpath(ge);
  3662.                 pge = ge->bkwd;
  3663.                 nge = ge->frwd;
  3664.  
  3665.                 df = ge->fpoints[i][2] - pge->fpoints[i][2];
  3666.  
  3667.                 iln = fabs(nge->fpoints[i][2] - ge->fpoints[i][2]);
  3668.                 oln = nge->fpoints[o][2] - ge->fpoints[o][2];
  3669.             }
  3670.  
  3671.             /* now check what do we have as previous/next line */
  3672.  
  3673.             if(ge != pge) { 
  3674.                 if( pge->type == GE_LINE && pge->fpoints[i][2] == pge->prev->fpoints[i][2]
  3675.                 && fabs(pge->fpoints[o][2] != pge->prev->fpoints[o][2]) ) {
  3676.                     if(ISDBG(STRAIGHTEN)) fprintf(stderr,"** straighten join with previous 0x%x 0x%x\n", pge, ge);
  3677.                     /* join the previous line with current */
  3678.                     pge->fx3 = ge->fx3;
  3679.                     pge->fy3 = ge->fy3;
  3680.  
  3681.                     ige = freethisge(ge)->prev; /* keep the iterator valid */
  3682.                     ge = pge;
  3683.                     fixendpath(ge);
  3684.                     pge = ge->bkwd;
  3685.                 }
  3686.             }
  3687.  
  3688.             if(ge != nge) { 
  3689.                 if (nge->type == GE_LINE && nge->fpoints[i][2] == ge->fpoints[i][2]
  3690.                 && fabs(nge->fpoints[o][2] != ge->fpoints[o][2]) ) {
  3691.                     if(ISDBG(STRAIGHTEN)) fprintf(stderr,"** straighten join with next 0x%x 0x%x\n", ge, nge);
  3692.                     /* join the next line with current */
  3693.                     ge->fx3 = nge->fx3;
  3694.                     ge->fy3 = nge->fy3;
  3695.  
  3696.                     freethisge(nge);
  3697.                     fixendpath(ge);
  3698.                     pge = ge->bkwd;
  3699.                     nge = ge->frwd;
  3700.  
  3701.                 }
  3702.             }
  3703.  
  3704.             if(ge != pge) { 
  3705.                 /* try to align the lines if neccessary */
  3706.                 if(df != 0.)
  3707.                     fclosegap(ge, ge, i, df, NULL);
  3708.             } else {
  3709.                 /* contour consists of only one line, get rid of it */
  3710.                 ige = freethisge(ge)->prev; /* keep the iterator valid */
  3711.             }
  3712.  
  3713.             break; /* don't bother looking at the other axis */
  3714.         }
  3715.     }
  3716. }
  3717.  
  3718. /* solve a square equation,
  3719.  * returns the number of solutions found, the solutions
  3720.  * are stored in res which should point to array of two doubles.
  3721.  * min and max limit the area for solutions
  3722.  */
  3723.  
  3724. static int
  3725. fsqequation(
  3726.     double a,
  3727.     double b,
  3728.     double c,
  3729.     double *res,
  3730.     double min,
  3731.     double max
  3732. )
  3733. {
  3734.     double D;
  3735.     int n;
  3736.  
  3737.     if(ISDBG(SQEQ)) fprintf(stderr, "sqeq(%g,%g,%g) [%g;%g]\n", a, b, c, min, max);
  3738.  
  3739.     if(fabs(a) < 0.000001) { /* if a linear equation */
  3740.         n=0;
  3741.         if(fabs(b) < 0.000001) /* not an equation at all */
  3742.             return 0;
  3743.         res[0] = -c/b;
  3744.         if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: linear t=%g\n", res[0]);
  3745.         if(res[0] >= min && res[0] <= max)
  3746.             n++;
  3747.         return n;
  3748.     }
  3749.  
  3750.     D = b*b - 4.0*a*c;
  3751.     if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: D=%g\n", D);
  3752.     if(D<0)
  3753.         return 0;
  3754.  
  3755.     D = sqrt(D);
  3756.  
  3757.     n=0;
  3758.     res[0] = (-b+D) / (2*a);
  3759.     if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: t1=%g\n", res[0]);
  3760.     if(res[0] >= min && res[0] <= max)
  3761.         n++;
  3762.  
  3763.     res[n] = (-b-D) / (2*a);
  3764.     if(ISDBG(SQEQ)) fprintf(stderr, "sqeq: t2=%g\n", res[n]);
  3765.     if(res[n] >= min && res[n] <= max)
  3766.         n++;
  3767.  
  3768.     /* return 2nd solution only if it's different enough */
  3769.     if(n==2 && fabs(res[0]-res[1])<0.000001)
  3770.         n=1;
  3771.  
  3772.     return n;
  3773. }
  3774.  
  3775. /* check that the curves don't cross quadrant boundary */
  3776. /* (float) */
  3777.  
  3778. /*
  3779.   Here we make sure that the curve does not continue past
  3780.   horizontal or vertical extremums. The horizontal points are
  3781.   explained, vertical points are by analogy.
  3782.  
  3783.   The horizontal points are where the derivative
  3784.   dy/dx is equal to 0. But the Bezier curves are defined by
  3785.   parametric formulas
  3786.    x=fx(t)
  3787.    y=fy(t)
  3788.   so finding this derivative is complicated.
  3789.   Also even if we find some point (x,y) splitting at this point
  3790.   is far not obvious. Fortunately we can use dy/dt = 0 instead,
  3791.   this gets to a rather simple square equation and splitting
  3792.   at a known value of t is simple.
  3793.  
  3794.   The formulas are:
  3795.  
  3796.   y = A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3
  3797.   y = (-A+3*B-3*C+D)*t^3 + (3*A-6*B+3*C)*t^2 + (-3*A+3*B)*t + A
  3798.   dy/dt = 3*(-A+3*B-3*C+D)*t^2 + 2*(3*A-6*B+3*C)*t + (-3*A+3*B)
  3799.  */
  3800.  
  3801. void
  3802. ffixquadrants(
  3803.     GLYPH *g
  3804. )
  3805. {
  3806.     GENTRY         *ge, *nge;
  3807.     int    i, j, np, oldnp;
  3808.     double    sp[5]; /* split points, last one empty */
  3809.     char dir[5]; /* for debugging, direction by which split happened */
  3810.     double a, b, *pts; /* points of a curve */
  3811.  
  3812.     for (ge = g->entries; ge != 0; ge = ge->next) {
  3813.         if (ge->type != GE_CURVE)
  3814.             continue;
  3815.         
  3816.     doagain:
  3817.         np = 0; /* no split points yet */
  3818.         if(ISDBG(QUAD)) {
  3819.             fprintf(stderr, "%s: trying 0x%x (%g %g) (%g %g) (%g %g) (%g %g)\n  ", g->name,
  3820.                 ge,  ge->prev->fx3, ge->prev->fy3, ge->fx1, ge->fy1, ge->fx2, ge->fy2,
  3821.                 ge->fx3, ge->fy3);
  3822.         }
  3823.         for(i=0; i<2; i++) { /* first for x then for y */
  3824.             /* find the cooridnates of control points */
  3825.             a = ge->prev->fpoints[i][2];
  3826.             pts = &ge->fpoints[i][0];
  3827.  
  3828.             oldnp = np;
  3829.             np += fsqequation(
  3830.                 3.0*(-a + 3.0*pts[0] - 3.0*pts[1] + pts[2]),
  3831.                 6.0*(a - 2.0*pts[0] + pts[1]),
  3832.                 3.0*(-a + pts[0]),
  3833.                 &sp[np],
  3834.                 0.0, 1.0); /* XXX range is [0;1] */
  3835.  
  3836.             if(np == oldnp)
  3837.                 continue;
  3838.  
  3839.             if(ISDBG(QUAD))
  3840.                 fprintf(stderr, "%s: 0x%x: %d pts(%c): ", 
  3841.                     g->name, ge, np-oldnp, i? 'y':'x');
  3842.  
  3843.             /* remove points that are too close to the ends 
  3844.              * because hor/vert ends are permitted, also
  3845.              * if the split point is VERY close to the ends
  3846.              * but not exactly then just flatten it and check again.
  3847.              */
  3848.             for(j = oldnp; j<np; j++) {
  3849.                 dir[j] = i;
  3850.                 if(ISDBG(QUAD))
  3851.                     fprintf(stderr, "%g ", sp[j]);
  3852.                 if(sp[j] < 0.03) { /* front end of curve */
  3853.                     if(ge->fpoints[i][0] != ge->prev->fpoints[i][2]) {
  3854.                         ge->fpoints[i][0] = ge->prev->fpoints[i][2];
  3855.                         if(ISDBG(QUAD)) fprintf(stderr, "flattened at front\n");
  3856.                         goto doagain;
  3857.                     }
  3858.                     if( ge->fpoints[i][1] != ge->fpoints[i][0]
  3859.                     && fsign(ge->fpoints[i][2] - ge->fpoints[i][1])
  3860.                             != fsign(ge->fpoints[i][1] - ge->fpoints[i][0]) ) {
  3861.                         ge->fpoints[i][1] = ge->fpoints[i][0];
  3862.                         if(ISDBG(QUAD)) fprintf(stderr, "flattened zigzag at front\n");
  3863.                         goto doagain;
  3864.                     }
  3865.                     sp[j] = sp[j+1]; np--; j--;
  3866.                     if(ISDBG(QUAD)) fprintf(stderr, "(front flat)  ");
  3867.                 } else if(sp[j] > 0.97) { /* rear end of curve */
  3868.                     if(ge->fpoints[i][1] != ge->fpoints[i][2]) {
  3869.                         ge->fpoints[i][1] = ge->fpoints[i][2];
  3870.                         if(ISDBG(QUAD)) fprintf(stderr, "flattened at rear\n");
  3871.                         goto doagain;
  3872.                     }
  3873.                     if( ge->fpoints[i][0] != ge->fpoints[i][1]
  3874.                     && fsign(ge->prev->fpoints[i][2] - ge->fpoints[i][0])
  3875.                             != fsign(ge->fpoints[i][0] - ge->fpoints[i][1]) ) {
  3876.                         ge->fpoints[i][0] = ge->fpoints[i][1];
  3877.                         if(ISDBG(QUAD)) fprintf(stderr, "flattened zigzag at rear\n");
  3878.                         goto doagain;
  3879.                     }
  3880.                     sp[j] = sp[j+1]; np--; j--;
  3881.                     if(ISDBG(QUAD)) fprintf(stderr, "(rear flat)  ");
  3882.                 } 
  3883.             }
  3884.             if(ISDBG(QUAD)) fprintf(stderr, "\n");
  3885.         }
  3886.  
  3887.         if(np==0) /* no split points, leave it alone */
  3888.             continue;
  3889.  
  3890.         if(ISDBG(QUAD)) {
  3891.             fprintf(stderr, "%s: splitting 0x%x (%g %g) (%g %g) (%g %g) (%g %g) at %d points\n  ", g->name,
  3892.                 ge,  ge->prev->fx3, ge->prev->fy3, ge->fx1, ge->fy1, ge->fx2, ge->fy2,
  3893.                 ge->fx3, ge->fy3, np);
  3894.             for(i=0; i<np; i++)
  3895.                 fprintf(stderr, "%g(%c) ", sp[i], dir[i] ? 'y':'x');
  3896.             fprintf(stderr, "\n");
  3897.         }
  3898.  
  3899.         /* sort the points ascending */
  3900.         for(i=0; i<np; i++)
  3901.             for(j=i+1; j<np; j++)
  3902.                 if(sp[i] > sp[j]) {
  3903.                     a = sp[i]; sp[i] = sp[j]; sp[j] = a;
  3904.                 }
  3905.  
  3906.         /* now finally do the split on each point */
  3907.         for(j=0; j<np; j++) {
  3908.             double k1, k2, c;
  3909.  
  3910.             k1 = sp[j];
  3911.             k2 = 1 - k1;
  3912.  
  3913.             if(ISDBG(QUAD)) fprintf(stderr, "   0x%x %g/%g\n", ge, k1, k2);
  3914.  
  3915.             nge = newgentry(GEF_FLOAT);
  3916.             (*nge) = (*ge);
  3917.  
  3918. #define SPLIT(pt1, pt2)    ( (pt1) + k1*((pt2)-(pt1)) ) /* order is important! */
  3919.             for(i=0; i<2; i++) { /* for x and y */
  3920.                 a = ge->fpoints[i][0]; /* get the middle points */
  3921.                 b = ge->fpoints[i][1];
  3922.  
  3923.                 /* calculate new internal points */
  3924.                 c = SPLIT(a, b);
  3925.  
  3926.                 ge->fpoints[i][0] = SPLIT(ge->prev->fpoints[i][2], a);
  3927.                 ge->fpoints[i][1] = SPLIT(ge->fpoints[i][0], c);
  3928.  
  3929.                 nge->fpoints[i][1] = SPLIT(b, nge->fpoints[i][2]);
  3930.                 nge->fpoints[i][0] = SPLIT(c, nge->fpoints[i][1]);
  3931.  
  3932.                 ge->fpoints[i][2] = SPLIT(ge->fpoints[i][1],
  3933.                     + nge->fpoints[i][0]);
  3934.             }
  3935. #undef SPLIT
  3936.  
  3937.             addgeafter(ge, nge);
  3938.  
  3939.             /* go to the next part, adjust remaining points */
  3940.             ge = nge;
  3941.             for(i=j+1; i<np; i++)
  3942.                 sp[i] = (sp[i]-k1) / k2;
  3943.         }
  3944.     }
  3945.  
  3946. }
  3947.  
  3948. /* check if a curve is a zigzag */
  3949.  
  3950. static int
  3951. iiszigzag(
  3952.     GENTRY *ge
  3953. ) 
  3954. {
  3955.     double          k, k1, k2;
  3956.     double          a, b;
  3957.  
  3958.     if (ge->type != GE_CURVE)
  3959.         return 0;
  3960.  
  3961.     a = ge->iy2 - ge->iy1;
  3962.     b = ge->ix2 - ge->ix1;
  3963.     k = fabs(a == 0 ? (b == 0 ? 1. : FBIGVAL) : (double) b / (double) a);
  3964.     a = ge->iy1 - ge->prev->iy3;
  3965.     b = ge->ix1 - ge->prev->ix3;
  3966.     k1 = fabs(a == 0 ? (b == 0 ? 1. : FBIGVAL) : (double) b / (double) a);
  3967.     a = ge->iy3 - ge->iy2;
  3968.     b = ge->ix3 - ge->ix2;
  3969.     k2 = fabs(a == 0 ? (b == 0 ? 1. : FBIGVAL) : (double) b / (double) a);
  3970.  
  3971.     /* if the curve is not a zigzag */
  3972.     if (k1 >= k && k2 <= k || k1 <= k && k2 >= k)
  3973.         return 0;
  3974.     else
  3975.         return 1;
  3976. }
  3977.  
  3978. /* check if a curve is a zigzag - floating */
  3979.  
  3980. static int
  3981. fiszigzag(
  3982.     GENTRY *ge
  3983. ) 
  3984. {
  3985.     double          k, k1, k2;
  3986.     double          a, b;
  3987.  
  3988.     if (ge->type != GE_CURVE)
  3989.         return 0;
  3990.  
  3991.     a = fabs(ge->fy2 - ge->fy1);
  3992.     b = fabs(ge->fx2 - ge->fx1);
  3993.     k = a < FEPS ? (b <FEPS ? 1. : FBIGVAL) : b / a;
  3994.     a = fabs(ge->fy1 - ge->prev->fy3);
  3995.     b = fabs(ge->fx1 - ge->prev->fx3);
  3996.     k1 = a < FEPS ? (b < FEPS ? 1. : FBIGVAL) : b / a;
  3997.     a = fabs(ge->fy3 - ge->fy2);
  3998.     b = fabs(ge->fx3 - ge->fx2);
  3999.     k2 = a < FEPS ? (b <FEPS ? 1. : FBIGVAL) : b / a;
  4000.  
  4001.     /* if the curve is not a zigzag */
  4002.     if (k1 >= k && k2 <= k || k1 <= k && k2 >= k)
  4003.         return 0;
  4004.     else
  4005.         return 1;
  4006. }
  4007.  
  4008. /* split the zigzag-like curves into two parts */
  4009.  
  4010. void
  4011. fsplitzigzags(
  4012.          GLYPH * g
  4013. )
  4014. {
  4015.     GENTRY         *ge, *nge;
  4016.     double          a, b, c, d;
  4017.  
  4018.     assertisfloat(g, "splitting zigzags");
  4019.     for (ge = g->entries; ge != 0; ge = ge->next) {
  4020.         if (ge->type != GE_CURVE)
  4021.             continue;
  4022.  
  4023.         /* if the curve is not a zigzag */
  4024.         if ( !fiszigzag(ge) ) {
  4025.             continue;
  4026.         }
  4027.  
  4028.         /* split the curve by t=0.5 */
  4029.         nge = newgentry(GEF_FLOAT);
  4030.         (*nge) = (*ge);
  4031.         nge->type = GE_CURVE;
  4032.  
  4033.         a = ge->prev->fx3;
  4034.         b = ge->fx1;
  4035.         c = ge->fx2;
  4036.         d = ge->fx3;
  4037.         nge->fx3 = d;
  4038.         nge->fx2 = (c + d) / 2.;
  4039.         nge->fx1 = (b + 2. * c + d) / 4.;
  4040.         ge->fx3 = (a + b * 3. + c * 3. + d) / 8.;
  4041.         ge->fx2 = (a + 2. * b + c) / 4.;
  4042.         ge->fx1 = (a + b) / 2.;
  4043.  
  4044.         a = ge->prev->fy3;
  4045.         b = ge->fy1;
  4046.         c = ge->fy2;
  4047.         d = ge->fy3;
  4048.         nge->fy3 = d;
  4049.         nge->fy2 = (c + d) / 2.;
  4050.         nge->fy1 = (b + 2. * c + d) / 4.;
  4051.         ge->fy3 = (a + b * 3. + c * 3. + d) / 8.;
  4052.         ge->fy2 = (a + 2. * b + c) / 4.;
  4053.         ge->fy1 = (a + b) / 2.;
  4054.  
  4055.         addgeafter(ge, nge);
  4056.     }
  4057. }
  4058.  
  4059. /* free this GENTRY, returns what was ge->next
  4060.  * (ge must be of type GE_LINE or GE_CURVE)
  4061.  * works on both float and int entries
  4062.  */
  4063.  
  4064. static GENTRY *
  4065. freethisge(
  4066.     GENTRY *ge
  4067. )
  4068. {
  4069.     GENTRY *xge;
  4070.  
  4071.     if (ge->bkwd != ge->prev) {
  4072.         /* at beginning of the contour */
  4073.  
  4074.         xge = ge->bkwd;
  4075.         if(xge == ge) { /* was the only line in contour */
  4076.             /* remove the contour completely */
  4077.             /* prev is GE_MOVE, next is GE_PATH, remove them all */
  4078.  
  4079.             /* may be the first contour, then ->bkwd points to ge->entries */
  4080.             if(ge->prev->prev == 0)
  4081.                 *(GENTRY **)(ge->prev->bkwd) = ge->next->next;
  4082.             else
  4083.                 ge->prev->prev->next = ge->next->next;
  4084.  
  4085.             if(ge->next->next) {
  4086.                 ge->next->next->prev = ge->prev->prev;
  4087.                 ge->next->next->bkwd = ge->prev->bkwd;
  4088.             }
  4089.  
  4090.             xge = ge->next->next;
  4091.             free(ge->prev); free(ge->next); free(ge);
  4092.             return xge;
  4093.         }
  4094.  
  4095.         /* move the start point of the contour */
  4096.         if(ge->flags & GEF_FLOAT) {
  4097.             ge->prev->fx3 = xge->fx3;
  4098.             ge->prev->fy3 = xge->fy3;
  4099.         } else {
  4100.             ge->prev->ix3 = xge->ix3;
  4101.             ge->prev->iy3 = xge->iy3;
  4102.         }
  4103.     } else if(ge->frwd != ge->next) {
  4104.         /* at end of the contour */
  4105.  
  4106.         xge = ge->frwd->prev;
  4107.         /* move the start point of the contour */
  4108.         if(ge->flags & GEF_FLOAT) {
  4109.             xge->fx3 = ge->bkwd->fx3;
  4110.             xge->fy3 = ge->bkwd->fy3;
  4111.         } else {
  4112.             xge->ix3 = ge->bkwd->ix3;
  4113.             xge->iy3 = ge->bkwd->iy3;
  4114.         }
  4115.     }
  4116.  
  4117.     ge->prev->next = ge->next;
  4118.     ge->next->prev = ge->prev;
  4119.     ge->bkwd->frwd = ge->frwd;
  4120.     ge->frwd->bkwd = ge->bkwd;
  4121.  
  4122.     xge = ge->next;
  4123.     free(ge);
  4124.     return xge;
  4125. }
  4126.  
  4127. /* inserts a new gentry (LINE or CURVE) after another (MOVE
  4128.  * or LINE or CURVE)
  4129.  * corrects the first GE_MOVE if neccessary
  4130.  */
  4131.  
  4132. static void
  4133. addgeafter(
  4134.     GENTRY *oge, /* after this */
  4135.     GENTRY *nge /* insert this */
  4136. )
  4137. {
  4138.     if(oge->type == GE_MOVE) {
  4139.         /* insert before next */
  4140.         if(oge->next->type == GE_PATH) {
  4141.             /* first and only GENTRY in path */
  4142.             nge->frwd = nge->bkwd = nge;
  4143.         } else {
  4144.             nge->frwd = oge->next;
  4145.             nge->bkwd = oge->next->bkwd;
  4146.             oge->next->bkwd->frwd = nge;
  4147.             oge->next->bkwd = nge;
  4148.         }
  4149.     } else {
  4150.         nge->frwd = oge->frwd;
  4151.         nge->bkwd = oge;
  4152.         oge->frwd->bkwd = nge;
  4153.         oge->frwd = nge;
  4154.     }
  4155.  
  4156.     nge->next = oge->next;
  4157.     nge->prev = oge;
  4158.     oge->next->prev = nge;
  4159.     oge->next = nge;
  4160.  
  4161.     if(nge->frwd->prev->type == GE_MOVE) {
  4162.         /* fix up the GE_MOVE entry */
  4163.         if(nge->flags & GEF_FLOAT) {
  4164.             nge->frwd->prev->fx3 = nge->fx3;
  4165.             nge->frwd->prev->fy3 = nge->fy3;
  4166.         } else {
  4167.             nge->frwd->prev->ix3 = nge->ix3;
  4168.             nge->frwd->prev->iy3 = nge->iy3;
  4169.         }
  4170.     }
  4171. }
  4172.  
  4173. /*
  4174.  * Check if this GENTRY happens to be at the end of path
  4175.  * and fix the first MOVETO accordingly
  4176.  * handles both int and float
  4177.  */
  4178.  
  4179. static void
  4180. fixendpath(
  4181.     GENTRY *ge
  4182. )
  4183. {
  4184.     GENTRY *mge;
  4185.  
  4186.     mge = ge->frwd->prev;
  4187.     if(mge->type == GE_MOVE) {
  4188.         if(ge->flags & GEF_FLOAT) {
  4189.             mge->fx3 = ge->fx3;
  4190.             mge->fy3 = ge->fy3;
  4191.         } else {
  4192.             mge->ix3 = ge->ix3;
  4193.             mge->iy3 = ge->iy3;
  4194.         }
  4195.     }
  4196. }
  4197.  
  4198. /*
  4199.  * This function adjusts the rest of path (the part from...to is NOT changed)
  4200.  * to cover the specified gap by the specified axis (0 - X, 1 - Y).
  4201.  * Gap is counted in direction (end_of_to - beginning_of_from).
  4202.  * Returns by how much the gap was not closed (0.0 if it was fully closed).
  4203.  * Ret contains by how much the first and last points of [from...to]
  4204.  * were moved to bring them in consistence to the rest of the path.
  4205.  * If ret==NULL then this info is not returned.
  4206.  */
  4207.  
  4208. static double
  4209. fclosegap(
  4210.     GENTRY *from,
  4211.     GENTRY *to,
  4212.     int axis,
  4213.     double gap,
  4214.     double *ret
  4215. )
  4216. {
  4217. #define TIMESLARGER 10.    /* how many times larger must be a curve to not change too much */
  4218.     double rm[2];
  4219.     double oldpos[2];
  4220.     double times, limit, df, dx;
  4221.     int j, k;
  4222.     GENTRY *xge, *pge, *nge, *bge[2];
  4223.  
  4224.     /* remember the old points to calculate ret */
  4225.     oldpos[0] = from->prev->fpoints[axis][2];
  4226.     oldpos[1] = to->fpoints[axis][2];
  4227.  
  4228.     rm[0] = rm[1] = gap / 2. ;
  4229.  
  4230.     bge[0] = from; /* this is convenient for iterations */
  4231.     bge[1] = to;
  4232.  
  4233.     /* first try to modify large curves but if have none then settle for small */
  4234.     for(times = (TIMESLARGER-1); times > 0.1; times /= 2. ) {
  4235.  
  4236.         if(rm[0]+rm[1] == 0.)
  4237.             break;
  4238.  
  4239.         /* iterate in both directions, backwards then forwards */
  4240.         for(j = 0; j<2; j++) {
  4241.  
  4242.             if(rm[j] == 0.) /* if this direction is exhausted */
  4243.                 continue;
  4244.  
  4245.             limit = fabs(rm[j]) * (1.+times);
  4246.  
  4247.             for(xge = bge[j]->cntr[j]; xge != bge[!j]; xge = xge->cntr[j]) {
  4248.                 dx = xge->fpoints[axis][2] - xge->prev->fpoints[axis][2];
  4249.                 df = fabs(dx) - limit;
  4250.                 if( df <= FEPS ) /* curve is too small to change */
  4251.                     continue;
  4252.  
  4253.                 if( df >= fabs(rm[j]) )
  4254.                     df = rm[j];
  4255.                 else 
  4256.                     df *= fsign(rm[j]); /* we may cover this part of rm */
  4257.  
  4258.                 rm[j] -= df;
  4259.                 limit = fabs(rm[j]) * (1.+times);
  4260.  
  4261.                 if(xge->type == GE_CURVE) { /* correct internal points */
  4262.                     double scale = ((dx+df) / dx) - 1.;
  4263.                     double base;
  4264.  
  4265.                     if(j)
  4266.                         base = xge->fpoints[axis][2];
  4267.                     else
  4268.                         base = xge->prev->fpoints[axis][2];
  4269.  
  4270.                     for(k = 0; k<2; k++)
  4271.                         xge->fpoints[axis][k] += scale * 
  4272.                             (xge->fpoints[axis][k] - base);
  4273.                 }
  4274.  
  4275.                 /* move all the intermediate lines */
  4276.                 if(j) {
  4277.                     df = -df; /* absolute direction */
  4278.                     pge = bge[1]->bkwd;
  4279.                     nge = xge->bkwd;
  4280.                 } else {
  4281.                     xge->fpoints[axis][2] += df;
  4282.                     pge = bge[0];
  4283.                     nge = xge->frwd;
  4284.                 }
  4285.                 while(nge != pge) {
  4286.                     if(nge->type == GE_CURVE) {
  4287.                         nge->fpoints[axis][0] +=df;
  4288.                         nge->fpoints[axis][1] +=df;
  4289.                     }
  4290.                     nge->fpoints[axis][2] += df;
  4291.                     if(nge->next != nge->frwd) { /* last entry of contour */
  4292.                         nge->frwd->prev->fpoints[axis][2] += df;
  4293.                     }
  4294.                     nge = nge->cntr[!j];
  4295.                 }
  4296.  
  4297.                 if(rm[j] == 0.)
  4298.                     break;
  4299.             }
  4300.         }
  4301.     }
  4302.  
  4303.     /* find the difference */
  4304.     oldpos[0] -= from->prev->fpoints[axis][2];
  4305.     oldpos[1] -= to->fpoints[axis][2];
  4306.  
  4307.     if(ret) {
  4308.         ret[0] = oldpos[0] - from->prev->fpoints[axis][2];
  4309.         ret[1] = oldpos[1] - to->fpoints[axis][2];
  4310.     }
  4311.  
  4312. #if 0
  4313.     if( rm[0]+rm[1] != gap - oldpos[1] + oldpos[0]) {
  4314.         fprintf(stderr, "** gap=%g rm[0]=%g rm[1]=%g o[0]=%g o[1]=%g rg=%g og=%g\n",
  4315.             gap, rm[0], rm[1], oldpos[0], oldpos[1], rm[0]+rm[1], 
  4316.             gap - oldpos[1] + oldpos[0]);
  4317.     }
  4318. #endif
  4319.  
  4320.     return rm[0]+rm[1];
  4321. #undef TIMESLARGER
  4322. }
  4323.  
  4324. /* remove the lines or curves smaller or equal to the size limit */
  4325.  
  4326. static void
  4327. fdelsmall(
  4328.     GLYPH *g,
  4329.     double minlen
  4330. )
  4331. {
  4332.     GENTRY  *ge, *nge, *pge, *xge, *next;
  4333.     int i, k;
  4334.     double dx, dy, d2, d2m;
  4335.     double minlen2;
  4336. #define TIMESLARGER 10.    /* how much larger must be a curve to not change too much */
  4337.  
  4338.     minlen2 = minlen*minlen;
  4339.  
  4340.     for (ge = g->entries; ge != 0; ge = next) {
  4341.         next = ge->next;
  4342.  
  4343.         if (ge->type != GE_CURVE && ge->type != GE_LINE)
  4344.             continue;
  4345.  
  4346.         d2m = 0;
  4347.         for(i= (ge->type==GE_CURVE? 0: 2); i<3; i++) {
  4348.             dx = ge->fxn[i] - ge->prev->fx3;
  4349.             dy = ge->fyn[i] - ge->prev->fy3;
  4350.             d2 = dx*dx + dy*dy;
  4351.             if(d2m < d2)
  4352.                 d2m = d2;
  4353.         }
  4354.  
  4355.         if( d2m > minlen2 ) { /* line is not too small */
  4356.             /* XXX add more normalization here */
  4357.             continue;
  4358.         }
  4359.  
  4360.         /* if the line is too small */
  4361.  
  4362.         /* check forwards if we have a whole sequence of them */
  4363.         nge = ge;
  4364.         for(xge = ge->frwd; xge != ge; xge = xge->frwd) {
  4365.             d2m = 0;
  4366.             for(i= (xge->type==GE_CURVE? 0: 2); i<3; i++) {
  4367.                 dx = xge->fxn[i] - xge->prev->fx3;
  4368.                 dy = xge->fyn[i] - xge->prev->fy3;
  4369.                 d2 = dx*dx + dy*dy;
  4370.                 if(d2m < d2)
  4371.                     d2m = d2;
  4372.             }
  4373.             if( d2m > minlen2 ) /* line is not too small */
  4374.                 break;
  4375.             nge = xge;
  4376.             if(next == nge) /* move the next step past this sequence */
  4377.                 next = next->next;
  4378.         }
  4379.  
  4380.         /* check backwards if we have a whole sequence of them */
  4381.         pge = ge;
  4382.         for(xge = ge->bkwd; xge != ge; xge = xge->bkwd) {
  4383.             d2m = 0;
  4384.             for(i= (xge->type==GE_CURVE? 0: 2); i<3; i++) {
  4385.                 dx = xge->fxn[i] - xge->prev->fx3;
  4386.                 dy = xge->fyn[i] - xge->prev->fy3;
  4387.                 d2 = dx*dx + dy*dy;
  4388.                 if(d2m < d2)
  4389.                     d2m = d2;
  4390.             }
  4391.             if( d2m > minlen2 ) /* line is not too small */
  4392.                 break;
  4393.             pge = xge;
  4394.         }
  4395.  
  4396.         /* now we have a sequence of small fragments in pge...nge (inclusive) */
  4397.  
  4398.         if(ISDBG(FCONCISE))  {
  4399.             fprintf(stderr, "glyph %s has very small fragments(%x..%x..%x)\n", 
  4400.             g->name, pge, ge, nge);
  4401.             dumppaths(g, pge, nge);
  4402.         }
  4403.  
  4404.         /* reduce whole sequence to one part and remember the middle point */
  4405.         if(pge != nge) {
  4406.             while(1) {
  4407.                 xge = pge->frwd;
  4408.                 if(xge == nge) {
  4409.                     pge->fx1 = pge->fx2 = pge->fx3;
  4410.                     pge->fx3 = nge->fx3;
  4411.                     pge->fy1 = pge->fy2 = pge->fy3;
  4412.                     pge->fy3 = nge->fy3;
  4413.                     pge->type = GE_CURVE;
  4414.                     freethisge(nge);
  4415.                     break;
  4416.                 }
  4417.                 if(xge == nge->bkwd) {
  4418.                     pge->fx1 = pge->fx2 = (pge->fx3+xge->fx3)/2.;
  4419.                     pge->fx3 = nge->fx3;
  4420.                     pge->fy1 = pge->fy2 = (pge->fy3+xge->fy3)/2.;
  4421.                     pge->fy3 = nge->fy3;
  4422.                     pge->type = GE_CURVE;
  4423.                     freethisge(nge);
  4424.                     freethisge(xge);
  4425.                     break;
  4426.                 }
  4427.                 freethisge(pge); pge = xge;
  4428.                 xge = nge->bkwd; freethisge(nge); nge = xge;
  4429.             }
  4430.         }
  4431.         ge = pge;
  4432.  
  4433.         /* check if the whole sequence is small */
  4434.         dx = ge->fx3 - ge->prev->fx3;
  4435.         dy = ge->fy3 - ge->prev->fy3;
  4436.         d2 = dx*dx + dy*dy;
  4437.  
  4438.         if( d2 > minlen2 ) { /* no, it is not */
  4439.             double b, d;
  4440.  
  4441.             WARNING_3 fprintf(stderr, "glyph %s had a sequence of fragments < %g points each, reduced to one curve\n",
  4442.                 g->name, minlen);
  4443.  
  4444.             /* check that we did not create a monstrosity spanning quadrants */
  4445.             if(fsign(ge->fx1 - ge->prev->fx1) * fsign(ge->fx3 - ge->fx1) < 0
  4446.             || fsign(ge->fy1 - ge->prev->fy1) * fsign(ge->fy3 - ge->fy1) < 0 ) { 
  4447.                 /* yes, we did; are both parts of this thing big enough ? */
  4448.                 dx = ge->fx1 - ge->prev->fx3;
  4449.                 dy = ge->fy1 - ge->prev->fy3;
  4450.                 d2 = dx*dx + dy*dy;
  4451.  
  4452.                 dx = ge->fx3 - ge->fx1;
  4453.                 dy = ge->fy3 - ge->fy1;
  4454.                 d2m = dx*dx + dy*dy;
  4455.  
  4456.                 if(d2 > minlen2 && d2m > minlen2) { /* make two straights */
  4457.                     nge = newgentry(GEF_FLOAT);
  4458.                     *nge = *ge;
  4459.                     
  4460.                     for(i=0; i<2; i++) {
  4461.                         ge->fpoints[i][2] = ge->fpoints[i][0];
  4462.                         b = nge->fpoints[i][0];
  4463.                         d = nge->fpoints[i][2] - b;
  4464.                         nge->fpoints[i][0] = b + 0.1*d;
  4465.                         nge->fpoints[i][1] = b + 0.9*d;
  4466.                     }
  4467.                 }
  4468.                 for(i=0; i<2; i++) { /* make one straight or first of two straights */
  4469.                     b = ge->prev->fpoints[i][2];
  4470.                     d = ge->fpoints[i][2] - b;
  4471.                     ge->fpoints[i][0] = b + 0.1*d;
  4472.                     ge->fpoints[i][1] = b + 0.9*d;
  4473.                 }
  4474.             }
  4475.             continue; 
  4476.         }
  4477.  
  4478.         if(ge->frwd == ge) { /* points to itself, just remove the path completely */
  4479.             WARNING_3 fprintf(stderr, "glyph %s had a path made of fragments < %g points each, removed\n",
  4480.                 g->name, minlen);
  4481.  
  4482.             next = freethisge(ge);
  4483.             continue;
  4484.         } 
  4485.  
  4486.         /* now close the gap by x and y */
  4487.         for(i=0; i<2; i++) {
  4488.             double gap;
  4489.  
  4490.             gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2];
  4491.             if( fclosegap(ge, ge, i, gap, NULL) != 0.0 ) {
  4492.                 double scale, base;
  4493.  
  4494.                 /* not good, as the last resort just scale the next line */
  4495.                 gap = ge->fpoints[i][2] - ge->prev->fpoints[i][2];
  4496.  
  4497.                 if(ISDBG(FCONCISE)) 
  4498.                     fprintf(stderr, "    last resort on %c: closing next by %g\n",
  4499.                     (i==0 ? 'x' : 'y'), gap);
  4500.  
  4501.                 nge = ge->frwd;
  4502.                 base = nge->fpoints[i][2];
  4503.                 dx = ge->fpoints[i][2] - base;
  4504.                 if(fabs(dx) < FEPS)
  4505.                     continue;
  4506.  
  4507.                 scale = ((dx-gap) / dx);
  4508.  
  4509.                 if(nge->type == GE_CURVE)
  4510.                     for(k = 0; k<2; k++)
  4511.                         nge->fpoints[i][k] = base + 
  4512.                             scale * (nge->fpoints[i][k] - base);
  4513.  
  4514.                 ge->fpoints[i][2] -= gap;
  4515.             }
  4516.         }
  4517.  
  4518.         /* OK, the gap is closed - remove this useless GENTRY */
  4519.         freethisge(ge);
  4520.     }
  4521. #undef TIMESLARGER
  4522. }
  4523.  
  4524. /* normalize curves to the form where their ends
  4525.  * can be safely used as derivatives
  4526.  */
  4527.  
  4528. static void
  4529. fnormalizec(
  4530.          GLYPH * g
  4531. )
  4532. {
  4533.     GENTRY *ge;
  4534.     int midsame, frontsame, rearsame, i;
  4535.     double d, b;
  4536.  
  4537.     assertisfloat(g, "normalizing curves");
  4538.  
  4539.     for (ge = g->entries; ge != 0; ge = ge->next) {
  4540.         if (ge->type != GE_CURVE)
  4541.             continue;
  4542.  
  4543.         midsame = (fabs(ge->fx1-ge->fx2)<FEPS && fabs(ge->fy1-ge->fy2)<FEPS);
  4544.         frontsame = (fabs(ge->fx1-ge->prev->fx3)<FEPS && fabs(ge->fy1-ge->prev->fy3)<FEPS);
  4545.         rearsame = (fabs(ge->fx3-ge->fx2)<FEPS && fabs(ge->fy3-ge->fy2)<FEPS);
  4546.  
  4547.         if(midsame && (frontsame || rearsame) ) {
  4548.             /* essentially a line */
  4549.             for(i=0; i<2; i++) {
  4550.                 b = ge->prev->fpoints[i][2];
  4551.                 d = ge->fpoints[i][2] - b;
  4552.                 ge->fpoints[i][0] = b + 0.1*d;
  4553.                 ge->fpoints[i][1] = b + 0.9*d;
  4554.             }
  4555.         } else if(frontsame) {
  4556.             for(i=0; i<2; i++) {
  4557.                 b = ge->prev->fpoints[i][2];
  4558.                 d = ge->fpoints[i][1] - b;
  4559.                 ge->fpoints[i][0] = b + 0.01*d;
  4560.             }
  4561.         } else if(rearsame) {
  4562.             for(i=0; i<2; i++) {
  4563.                 b = ge->fpoints[i][2];
  4564.                 d = ge->fpoints[i][0] - b;
  4565.                 ge->fpoints[i][1] = b + 0.01*d;
  4566.             }
  4567.         } else
  4568.             continue;
  4569.  
  4570.         if(ISDBG(FCONCISE)) fprintf(stderr, "glyph %g, normalized entry %x\n", g->name, ge);
  4571.     }
  4572. }
  4573.  
  4574. /* find the point where two rays continuing vectors cross
  4575.  * rays are defined as beginning of curve1 and end of curve 2
  4576.  * returns 1 if they cross, 0 if they don't
  4577.  * If they cross returns the maximal scales for both vectors.
  4578.  * Expects that the curves are normalized.
  4579.  */
  4580.  
  4581. static int
  4582. fcrossrays(
  4583.     GENTRY *ge1,
  4584.     GENTRY *ge2,
  4585.     double *max1,
  4586.     double *max2
  4587. )
  4588. {
  4589.     struct ray {
  4590.         double x1, y1, x2, y2;
  4591.         int isvert;
  4592.         double k, b; /* lines are represented as y = k*x + b */
  4593.         double *maxp;
  4594.     } ray [3];
  4595.     double x, y;
  4596.     int i;
  4597.  
  4598.     ray[0].x1 = ge1->prev->fx3;
  4599.     ray[0].y1 = ge1->prev->fy3;
  4600.     ray[0].x2 = ge1->fx1;
  4601.     ray[0].y2 = ge1->fy1;
  4602.     ray[0].maxp = max1;
  4603.  
  4604.     ray[1].x1 = ge2->fx3;
  4605.     ray[1].y1 = ge2->fy3;
  4606.     ray[1].x2 = ge2->fx2;
  4607.     ray[1].y2 = ge2->fy2;
  4608.     ray[1].maxp = max2;
  4609.  
  4610.     for(i=0; i<2; i++) {
  4611.         if(ray[i].x1 == ray[i].x2) 
  4612.             ray[i].isvert = 1;
  4613.         else {
  4614.             ray[i].isvert = 0;
  4615.             ray[i].k = (ray[i].y2 - ray[i].y1) / (ray[i].x2 - ray[i].x1);
  4616.             ray[i].b = ray[i].y2 - ray[i].k * ray[i].x2;
  4617.         }
  4618.     }
  4619.  
  4620.     if(ray[0].isvert && ray[1].isvert) {
  4621.         if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: both vertical\n");
  4622.         return 0; /* both vertical, don't cross */
  4623.     }
  4624.  
  4625.     if(ray[1].isvert) {
  4626.         ray[2] = ray[0]; /* exchange them */
  4627.         ray[0] = ray[1];
  4628.         ray[1] = ray[2];
  4629.     }
  4630.  
  4631.     if(ray[0].isvert) {
  4632.         x = ray[0].x1;
  4633.     } else {
  4634.         if( fabs(ray[0].k - ray[1].k) < FEPS) {
  4635.             if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: parallel lines, k = %g, %g\n",
  4636.                 ray[0].k, ray[1].k);
  4637.             return 0; /* parallel lines */
  4638.         }
  4639.         x = (ray[1].b - ray[0].b) / (ray[0].k - ray[1].k) ;
  4640.     }
  4641.     y = ray[1].k * x + ray[1].b;
  4642.  
  4643.     for(i=0; i<2; i++) {
  4644.         if(ray[i].isvert)
  4645.             *ray[i].maxp = (y - ray[i].y1) / (ray[i].y2 - ray[i].y1);
  4646.         else
  4647.             *ray[i].maxp = (x - ray[i].x1) / (ray[i].x2 - ray[i].x1);
  4648.         /* check if wrong sides of rays cross */
  4649.         if( *ray[i].maxp < 0 ) {
  4650.             if(ISDBG(FCONCISE)) fprintf(stderr, "crossrays: scale=%g @(%g,%g) (%g,%g)<-(%g,%g)\n",
  4651.                 *ray[i].maxp, x, y, ray[i].x2, ray[i].y2, ray[i].x1, ray[i].y1);
  4652.             return 0;
  4653.         }
  4654.     }
  4655.     return 1;
  4656. }
  4657.  
  4658. /* find the area covered by the curve
  4659.  * (limited by the projections to the X axis)
  4660.  */
  4661.  
  4662. static double
  4663. fcvarea(
  4664.     GENTRY *ge
  4665. )
  4666. {
  4667.     double Ly, My, Ny, Py, Qx, Rx, Sx;
  4668.     double area;
  4669.  
  4670.     /* y = Ly*t^3 + My*t^2 + Ny*t + Py */
  4671.     Ly = -ge->prev->fy3 + 3*(ge->fy1 - ge->fy2) + ge->fy3;
  4672.     My = 3*ge->prev->fy3 - 6*ge->fy1 + 3*ge->fy2;
  4673.     Ny = 3*(-ge->prev->fy3 + ge->fy1);
  4674.     Py = ge->prev->fy3;
  4675.  
  4676.     /* dx/dt = Qx*t^2 + Rx*t + Sx */
  4677.     Qx = 3*(-ge->prev->fx3 + 3*(ge->fx1 - ge->fx2) + ge->fx3);
  4678.     Rx = 6*(ge->prev->fx3 - 2*ge->fx1 + ge->fx2);
  4679.     Sx = 3*(-ge->prev->fx3 + ge->fx1);
  4680.  
  4681.     /* area is integral[from 0 to 1]( y(t) * dx(t)/dt *dt) */
  4682.     area = 1./6.*(Ly*Qx) + 1./5.*(Ly*Rx + My*Qx) 
  4683.         + 1./4.*(Ly*Sx + My*Rx + Ny*Qx) + 1./3.*(My*Sx + Ny*Rx + Py*Qx)
  4684.         + 1./2.*(Ny*Sx + Py*Rx) + Py*Sx;
  4685.  
  4686.     return area;
  4687. }
  4688.  
  4689. /* find the value of point on the curve at the given parameter t,
  4690.  * along the given axis (0 - X, 1 - Y).
  4691.  */
  4692.  
  4693. static double
  4694. fcvval(
  4695.     GENTRY *ge,
  4696.     int axis,
  4697.     double t
  4698. )
  4699. {
  4700.     double t2, mt, mt2;
  4701.  
  4702.     /* val = A*(1-t)^3 + 3*B*(1-t)^2*t + 3*C*(1-t)*t^2 + D*t^3 */
  4703.     t2 = t*t;
  4704.     mt = 1-t;
  4705.     mt2 = mt*mt;
  4706.     
  4707.     return ge->prev->fpoints[axis][2]*mt2*mt 
  4708.         + 3*(ge->fpoints[axis][0]*mt2*t + ge->fpoints[axis][1]*mt*t2)
  4709.         + ge->fpoints[axis][2]*t*t2;
  4710. }
  4711.  
  4712. /* Check that the new curve has the point identified by the 
  4713.  * parameter t reasonably close to the corresponding point
  4714.  * in the old pair of curves which were joined in proportion k.
  4715.  * If old2 is NULL then just compare nge and old1 at the point t.
  4716.  * Returns 0 if OK, 1 if it's too far.
  4717.  */
  4718.  
  4719. static int
  4720. fckjoinedcv(
  4721.     GLYPH *g,
  4722.     double t,
  4723.     GENTRY *nge,
  4724.     GENTRY *old1,
  4725.     GENTRY *old2,
  4726.     double k
  4727. )
  4728. {
  4729.     GENTRY *oge;
  4730.     double ot;
  4731.     double off;
  4732.     double lim;
  4733.     int i;
  4734.  
  4735.     if(old2 == 0) {
  4736.         oge = old1;
  4737.         ot = t;
  4738.     } else if(t <= k && k!=0.) {
  4739.         oge = old1;
  4740.         ot = t/k;
  4741.     } else {
  4742.         oge = old2;
  4743.         ot = (t-k) / (1.-k);
  4744.     }
  4745.  
  4746.     if(ISDBG(FCONCISE))
  4747.         fprintf(stderr, "%s: t=%g ot=%g (%x) ", g->name, t, ot, oge);
  4748.  
  4749.     for(i=0; i<2; i++) {
  4750.         /* permitted tolerance is 5% */
  4751.         lim = fabs(nge->fpoints[i][2] - nge->prev->fpoints[i][2])*0.05;
  4752.  
  4753.         if(lim < 3.)
  4754.             lim = 3.; /* for small curves the tolerance is higher */
  4755.         if(lim > 10.)
  4756.             lim = 10.; /* for big curves the tolerance is limited anyway */
  4757.  
  4758.         off = fabs(fcvval(nge, i, t) - fcvval(oge, i, ot));
  4759.  
  4760.         if(off > lim) {
  4761.             if(ISDBG(FCONCISE))
  4762.                 fprintf(stderr, "out of range d%c=%.2f(%.2f)\n", 
  4763.                     (i==0 ? 'X' : 'Y'), off, lim);
  4764.             return 1;
  4765.         }
  4766.  
  4767.         if(ISDBG(FCONCISE))
  4768.             fprintf(stderr, "valid d%c=%.2f(%.2f)  ", (i==0 ? 'X' : 'Y'), off, lim);
  4769.     }
  4770.     if(ISDBG(FCONCISE))
  4771.         fprintf(stderr, "\n");
  4772.     return 0;
  4773. }
  4774.  
  4775. /* force conciseness: substitute 2 or more curves going in the
  4776. ** same quadrant with one curve
  4777. ** in floating point
  4778. */
  4779.  
  4780. void
  4781. fforceconcise(
  4782.          GLYPH * g
  4783. )
  4784. {
  4785.     GENTRY         *ge, *nge;
  4786.     GENTRY          tge;
  4787.     double          firstlen, lastlen, sumlen, scale;
  4788.     double          dxw1, dyw1, dxw2, dyw2;
  4789.     double          dxb1, dyb1, dxe1, dye1;
  4790.     double          dxb2, dyb2, dxe2, dye2;
  4791.     double          maxsc1, maxsc2;
  4792.     int             i;
  4793.  
  4794.     assertisfloat(g, "enforcing conciseness");
  4795.  
  4796.     fdelsmall(g, 0.05);
  4797.     assertpath(g->entries, __FILE__, __LINE__, g->name);
  4798.     fnormalizec(g);
  4799.  
  4800.  
  4801.     for (ge = g->entries; ge != 0; ge = ge->next) {
  4802.         if (ge->type != GE_CURVE)
  4803.             continue;
  4804.  
  4805.         /* the whole direction of curve */
  4806.         dxw1 = ge->fx3 - ge->prev->fx3;
  4807.         dyw1 = ge->fy3 - ge->prev->fy3;
  4808.  
  4809.         while (1) {
  4810.             /* the whole direction of curve */
  4811.             dxw1 = ge->fx3 - ge->prev->fx3;
  4812.             dyw1 = ge->fy3 - ge->prev->fy3;
  4813.  
  4814.             /* directions of  ends of curve */
  4815.             dxb1 = ge->fx1 - ge->prev->fx3;
  4816.             dyb1 = ge->fy1 - ge->prev->fy3;
  4817.             dxe1 = ge->fx3 - ge->fx2;
  4818.             dye1 = ge->fy3 - ge->fy2;
  4819.  
  4820.             nge = ge->frwd;
  4821.  
  4822.             if (nge->type != GE_CURVE)
  4823.                 break;
  4824.  
  4825.             dxw2 = nge->fx3 - ge->fx3;
  4826.             dyw2 = nge->fy3 - ge->fy3;
  4827.  
  4828.             dxb2 = nge->fx1 - ge->fx3;
  4829.             dyb2 = nge->fy1 - ge->fy3;
  4830.             dxe2 = nge->fx3 - nge->fx2;
  4831.             dye2 = nge->fy3 - nge->fy2;
  4832.  
  4833.             /* if curve changes direction */
  4834.             if (fsign(dxw1) != fsign(dxw2) || fsign(dyw1) != fsign(dyw2))
  4835.                 break;
  4836.  
  4837.             /* if the arch is going in other direction */
  4838.             if (fsign(fabs(dxb1 * dyw1) - fabs(dyb1 * dxw1))
  4839.                 * fsign(fabs(dxe2 * dyw2) - fabs(dye2 * dxw2)) > 0)
  4840.                 break;
  4841.  
  4842.             /* get possible scale limits within which we won't cross quadrants */
  4843.             if( fcrossrays(ge, nge, &maxsc1, &maxsc2) == 0 ) {
  4844.                 if(ISDBG(FCONCISE)) {
  4845.                     fprintf(stderr, "glyph %s has curves with strange ends\n", g->name);
  4846.                     dumppaths(g, ge, nge);
  4847.                 }
  4848.                 break;
  4849.             }
  4850.  
  4851.             if(maxsc1 < 1. || maxsc2 < 1. ) /* would create a zigzag */
  4852.                 break;
  4853.  
  4854.             ge->dir = fgetcvdir(ge);
  4855.             nge->dir = fgetcvdir(nge);
  4856.  
  4857.             if( ((ge->dir&CVDIR_FRONT)-CVDIR_FEQUAL) * ((nge->dir&CVDIR_REAR)-CVDIR_REQUAL) < 0 )
  4858.                 /* would create a zigzag */
  4859.                 break;
  4860.  
  4861.             firstlen = sqrt( dxe1*dxe1 + dye1*dye1 );
  4862.             lastlen = sqrt( dxb2*dxb2 + dyb2*dyb2 );
  4863.             sumlen = firstlen + lastlen;
  4864.  
  4865.             /* check the scale limits */
  4866.             if( sumlen/firstlen > maxsc1 || sumlen/lastlen > maxsc2 ) {
  4867.                 if(ISDBG(FCONCISE)) 
  4868.                     fprintf(stderr, "%s: %x, %x would be crossing in forceconcise\n", 
  4869.                     g->name, ge, nge);
  4870.                 break;
  4871.             }
  4872.  
  4873.             /* OK, it seems like we can attempt to join these two curves */
  4874.             tge.flags = ge->flags;
  4875.             tge.prev = ge->prev;
  4876.             tge.fx1 = ge->fx1;
  4877.             tge.fy1 = ge->fy1;
  4878.             tge.fx2 = nge->fx2;
  4879.             tge.fy2 = nge->fy2;
  4880.             tge.fx3 = nge->fx3;
  4881.             tge.fy3 = nge->fy3;
  4882.  
  4883.             dxb1 = tge.fx1 - tge.prev->fx3;
  4884.             dyb1 = tge.fy1 - tge.prev->fy3;
  4885.             dxe1 = tge.fx3 - tge.fx2;
  4886.             dye1 = tge.fy3 - tge.fy2;
  4887.  
  4888.             /* scale the first segment */
  4889.             scale = sumlen / firstlen;
  4890.             tge.fx1 = tge.prev->fx3 + scale * dxb1;
  4891.             tge.fy1 = tge.prev->fy3 + scale * dyb1;
  4892.  
  4893.             /* scale the last segment */
  4894.             scale = sumlen / lastlen;
  4895.             tge.fx2 = tge.fx3 - scale * dxe1;
  4896.             tge.fy2 = tge.fy3 - scale * dye1;
  4897.  
  4898.             /* now check if we got something sensible */
  4899.  
  4900.             /* check if some important points is too far from original */
  4901.             scale = firstlen / sumlen;
  4902.             {
  4903.                 double pts[4] = { 0./*will be replaced*/, 0.5, 0.25, 0.75 };
  4904.                 int i, bad;
  4905.  
  4906.                 pts[0] = scale;
  4907.                 bad = 0;
  4908.  
  4909.                 for(i=0; i<sizeof(pts)/sizeof(pts[0]); i++)
  4910.                     if(fckjoinedcv(g, pts[i], &tge, ge, nge, scale)) {
  4911.                         bad = 1;
  4912.                         break;
  4913.                     }
  4914.                 if(bad)
  4915.                     break;
  4916.             }
  4917.  
  4918.             /* OK, it looks reasonably, let's apply it */
  4919.             if(ISDBG(FCONCISE)) 
  4920.                 dumppaths(g, ge, nge);
  4921.  
  4922.             for(i=0; i<3; i++) {
  4923.                 ge->fxn[i] = tge.fxn[i];
  4924.                 ge->fyn[i] = tge.fyn[i];
  4925.             }
  4926.  
  4927.             freethisge(nge);
  4928.         }
  4929.     }
  4930. }
  4931.  
  4932. void
  4933. print_glyph(
  4934.        int glyphno
  4935. )
  4936. {
  4937.     GLYPH          *g;
  4938.     GENTRY         *ge;
  4939.     int             x = 0, y = 0;
  4940.     int             i;
  4941.     int             grp, lastgrp= -1;
  4942.  
  4943.     g = &glyph_list[glyphno];
  4944.  
  4945.     fprintf(pfa_file, "/%s { \n", g->name);
  4946.  
  4947.     /* consider widths >MAXLEGALWIDTH as bugs */
  4948.     if( g->scaledwidth <= MAXLEGALWIDTH ) {
  4949.         fprintf(pfa_file, "0 %d hsbw\n", g->scaledwidth);
  4950.     } else {
  4951.         fprintf(pfa_file, "0 1000 hsbw\n");
  4952.         WARNING_2 fprintf(stderr, "glyph %s: width %d seems to be buggy, set to 1000\n",
  4953.             g->name, g->scaledwidth);
  4954.     }
  4955.  
  4956. #if 0
  4957.     fprintf(pfa_file, "%% contours: ");
  4958.     for (i = 0; i < g->ncontours; i++)
  4959.         fprintf(pfa_file, "%s(%d,%d) ", (g->contours[i].direction == DIR_OUTER ? "out" : "in"),
  4960.             g->contours[i].xofmin, g->contours[i].ymin);
  4961.     fprintf(pfa_file, "\n");
  4962.  
  4963.     if (g->rymin < 5000)
  4964.         fprintf(pfa_file, "%d lower%s\n", g->rymin, (g->flatymin ? "flat" : "curve"));
  4965.     if (g->rymax > -5000)
  4966.         fprintf(pfa_file, "%d upper%s\n", g->rymax, (g->flatymax ? "flat" : "curve"));
  4967. #endif
  4968.  
  4969.     if (g->hstems)
  4970.         for (i = 0; i < g->nhs; i += 2) {
  4971.             if (g->hstems[i].flags & ST_3) {
  4972.                 fprintf(pfa_file, "%d %d %d %d %d %d hstem3\n",
  4973.                     g->hstems[i].value,
  4974.                 g->hstems[i + 1].value - g->hstems[i].value,
  4975.                     g->hstems[i + 2].value,
  4976.                     g->hstems[i + 3].value - g->hstems[i + 2].value,
  4977.                     g->hstems[i + 4].value,
  4978.                     g->hstems[i + 5].value - g->hstems[i + 4].value
  4979.                     );
  4980.                 i += 4;
  4981.             } else {
  4982.                 fprintf(pfa_file, "%d %d hstem\n", g->hstems[i].value,
  4983.                 g->hstems[i + 1].value - g->hstems[i].value);
  4984.             }
  4985.         }
  4986.  
  4987.     if (g->vstems)
  4988.         for (i = 0; i < g->nvs; i += 2) {
  4989.             if (g->vstems[i].flags & ST_3) {
  4990.                 fprintf(pfa_file, "%d %d %d %d %d %d vstem3\n",
  4991.                     g->vstems[i].value,
  4992.                 g->vstems[i + 1].value - g->vstems[i].value,
  4993.                     g->vstems[i + 2].value,
  4994.                     g->vstems[i + 3].value - g->vstems[i + 2].value,
  4995.                     g->vstems[i + 4].value,
  4996.                     g->vstems[i + 5].value - g->vstems[i + 4].value
  4997.                     );
  4998.                 i += 4;
  4999.             } else {
  5000.                 fprintf(pfa_file, "%d %d vstem\n", g->vstems[i].value,
  5001.                 g->vstems[i + 1].value - g->vstems[i].value);
  5002.             }
  5003.         }
  5004.  
  5005.     for (ge = g->entries; ge != 0; ge = ge->next) {
  5006.         if(g->nsg>0) {
  5007.             grp=ge->stemid;
  5008.             if(grp >= 0 && grp != lastgrp)  {
  5009.                 fprintf(pfa_file, "%d 4 callsubr\n", grp+g->firstsubr);
  5010.                 lastgrp=grp;
  5011.             }
  5012.         }
  5013.  
  5014.         switch (ge->type) {
  5015.         case GE_MOVE:
  5016.             if (absolute)
  5017.                 fprintf(pfa_file, "%d %d amoveto\n", ge->ix3, ge->iy3);
  5018.             else
  5019.                 rmoveto(ge->ix3 - x, ge->iy3 - y);
  5020.             if (0)
  5021.                 fprintf(stderr, "Glyph %s: print moveto(%d, %d)\n",
  5022.                     g->name, ge->ix3, ge->iy3);
  5023.             x = ge->ix3;
  5024.             y = ge->iy3;
  5025.             break;
  5026.         case GE_LINE:
  5027.             if (absolute)
  5028.                 fprintf(pfa_file, "%d %d alineto\n", ge->ix3, ge->iy3);
  5029.             else
  5030.                 rlineto(ge->ix3 - x, ge->iy3 - y);
  5031.             x = ge->ix3;
  5032.             y = ge->iy3;
  5033.             break;
  5034.         case GE_CURVE:
  5035.             if (absolute)
  5036.                 fprintf(pfa_file, "%d %d %d %d %d %d arcurveto\n",
  5037.                     ge->ix1, ge->iy1, ge->ix2, ge->iy2, ge->ix3, ge->iy3);
  5038.             else
  5039.                 rrcurveto(ge->ix1 - x, ge->iy1 - y,
  5040.                       ge->ix2 - ge->ix1, ge->iy2 - ge->iy1,
  5041.                       ge->ix3 - ge->ix2, ge->iy3 - ge->iy2);
  5042.             x = ge->ix3;
  5043.             y = ge->iy3;
  5044.             break;
  5045.         case GE_PATH:
  5046.             closepath();
  5047.             break;
  5048.         default:
  5049.             WARNING_1 fprintf(stderr, "**** Glyph %s: unknown entry type '%c'\n",
  5050.                 g->name, ge->type);
  5051.             break;
  5052.         }
  5053.     }
  5054.  
  5055.     fprintf(pfa_file, "endchar } ND\n");
  5056. }
  5057.  
  5058. /* print the subroutines for this glyph, returns the number of them */
  5059. int
  5060. print_glyph_subs(
  5061.        int glyphno,
  5062.        int startid /* start numbering subroutines from this id */
  5063. )
  5064. {
  5065.     GLYPH *g;
  5066.     int i, grp;
  5067.  
  5068.     g = &glyph_list[glyphno];
  5069.  
  5070.     if(!hints || !subhints || g->nsg<1)
  5071.         return 0;
  5072.  
  5073.     g->firstsubr=startid;
  5074.  
  5075. #if 0
  5076.     fprintf(pfa_file, "%% %s %d\n", g->name, g->nsg);
  5077. #endif
  5078.     for(grp=0; grp<g->nsg; grp++) {
  5079.         fprintf(pfa_file, "dup %d {\n", startid++);
  5080.         for(i= (grp==0)? 0 : g->nsbs[grp-1]; i<g->nsbs[grp]; i++)
  5081.             fprintf(pfa_file, "\t%d %d %cstem\n", g->sbstems[i].low, 
  5082.                 g->sbstems[i].high-g->sbstems[i].low,
  5083.                 g->sbstems[i].isvert ? 'v' : 'h');
  5084.         fprintf(pfa_file, "\treturn\n\t} NP\n");
  5085.     }
  5086.  
  5087.     return g->nsg;
  5088. }
  5089.  
  5090. void
  5091. print_glyph_metrics(
  5092.        int code,
  5093.        int glyphno
  5094. )
  5095. {
  5096.     GLYPH *g;
  5097.  
  5098.     g = &glyph_list[glyphno];
  5099.  
  5100.     if(transform)
  5101.       fprintf(afm_file, "C %d ; WX %d ; N %s ; B %d %d %d %d ;\n",
  5102.           code, g->scaledwidth, g->name,
  5103.           iscale(g->xMin), iscale(g->yMin), iscale(g->xMax), iscale(g->yMax));
  5104.     else
  5105.       fprintf(afm_file, "C %d ; WX %d ; N %s ; B %d %d %d %d ;\n",
  5106.           code, g->scaledwidth, g->name,
  5107.           g->xMin, g->yMin, g->xMax, g->yMax);
  5108. }
  5109.  
  5110. /*
  5111.  SB:
  5112.  An important note about the BlueValues.
  5113.  
  5114.  The Adobe documentation says that the maximal width of a Blue zone
  5115.  is connected to the value of BlueScale, which is by default 0.039625.
  5116.  The BlueScale value defines, at which point size the overshoot
  5117.  suppression be disabled.
  5118.  
  5119.  The formula for it that is given in the manual is:
  5120.  
  5121.   BlueScale=point_size/240, for a 300dpi device
  5122.  
  5123.  that makes us wonder what is this 240 standing for. Incidentally
  5124.  240=72*1000/300, where 72 is the relation between inches and points,
  5125.  1000 is the size of the glyph matrix, and 300dpi is the resolution of
  5126.  the output device. Knowing that we can recalculate the formula for
  5127.  the font size in pixels rather than points:
  5128.  
  5129.   BlueScale=pixel_size/1000
  5130.  
  5131.  That looks a lot simpler than the original formula, does not it ?
  5132.  And the limitation about the maximal width of zone also looks
  5133.  a lot simpler after the transformation:
  5134.  
  5135.   max_width < 1000/pixel_size
  5136.  
  5137.  that ensures that even at the maximal pixel size when the overshoot
  5138.  suppression is disabled the zone width will be less than one pixel.
  5139.  This is important, failure to comply to this limit will result in
  5140.  really ugly fonts (been there, done that). But knowing the formula
  5141.  for the pixel width, we see that in fact we can use the maximal width
  5142.  of 24, not 23 as specified in the manual.
  5143.  
  5144. */
  5145.  
  5146. #define MAXBLUEWIDTH (24)
  5147.  
  5148. /*
  5149.  * Find the indexes of the most frequent values
  5150.  * in the hystogram, sort them in ascending order, and save which one
  5151.  * was the best one (if asked).
  5152.  * Returns the number of values found (may be less than maximal because
  5153.  * we ignore the zero values)
  5154.  */
  5155.  
  5156. #define MAXHYST    (2000)        /* size of the hystogram */
  5157. #define HYSTBASE 500
  5158.  
  5159. static int
  5160. besthyst(
  5161.      int *hyst,        /* the hystogram */
  5162.      int base,        /* the base point of the hystogram */
  5163.      int *best,        /* the array for indexes of best values */
  5164.      int nbest,        /* its allocated size */
  5165.      int width,        /* minimal difference between indexes */
  5166.      int *bestindp        /* returned top point */
  5167. )
  5168. {
  5169.     unsigned char   hused[MAXHYST / 8 + 1];
  5170.     int             i, max, j, w, last = 0;
  5171.     int             nf = 0;
  5172.  
  5173.     width--;
  5174.  
  5175.     memset(hused, 0 , sizeof hused);
  5176.  
  5177.     max = 1;
  5178.     for (i = 0; i < nbest && max != 0; i++) {
  5179.         best[i] = 0;
  5180.         max = 0;
  5181.         for (j = 1; j < MAXHYST - 1; j++) {
  5182.             w = hyst[j];
  5183.  
  5184.             if (w > max && (hused[j>>3] & (1 << (j & 0x07))) == 0) {
  5185.                 best[i] = j;
  5186.                 max = w;
  5187.             }
  5188.         }
  5189.         if (max != 0) {
  5190.             if (max < last/2) {
  5191.                 /* do not pick the too low values */
  5192.                 break;
  5193.             }
  5194.             for (j = best[i] - width; j <= best[i] + width; j++) {
  5195.                 if (j >= 0 && j < MAXHYST)
  5196.                     hused[j >> 3] |= (1 << (j & 0x07));
  5197.             }
  5198.             last = max;
  5199.             best[i] -= base;
  5200.             nf = i + 1;
  5201.         }
  5202.     }
  5203.  
  5204.     if (bestindp)
  5205.         *bestindp = best[0];
  5206.  
  5207.     /* sort the indexes in ascending order */
  5208.     for (i = 0; i < nf; i++) {
  5209.         for (j = i + 1; j < nf; j++)
  5210.             if (best[j] < best[i]) {
  5211.                 w = best[i];
  5212.                 best[i] = best[j];
  5213.                 best[j] = w;
  5214.             }
  5215.     }
  5216.  
  5217.     return nf;
  5218. }
  5219.  
  5220. /*
  5221.  * Find the next best Blue zone in the hystogram.
  5222.  * Return the weight of the found zone.
  5223.  */
  5224.  
  5225. static int
  5226. bestblue(
  5227.      short *zhyst,        /* the zones hystogram */
  5228.      short *physt,        /* the points hystogram */
  5229.      short *ozhyst,        /* the other zones hystogram */
  5230.      int *bluetab        /* where to put the found zone */
  5231. )
  5232. {
  5233.     int             i, j, w, max, ind, first, last;
  5234.  
  5235.     /* find the highest point in the zones hystogram */
  5236.     /* if we have a plateau, take its center */
  5237.     /* if we have multiple peaks, take the first one */
  5238.  
  5239.     max = -1;
  5240.     first = last = -10;
  5241.     for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
  5242.         w = zhyst[i];
  5243.         if (w > max) {
  5244.             first = last = i;
  5245.             max = w;
  5246.         } else if (w == max) {
  5247.             if (last == i - 1)
  5248.                 last = i;
  5249.         }
  5250.     }
  5251.     ind = (first + last) / 2;
  5252.  
  5253.     if (max == 0)        /* no zones left */
  5254.         return 0;
  5255.  
  5256.     /* now we reuse `first' and `last' as inclusive borders of the zone */
  5257.     first = ind;
  5258.     last = ind + (MAXBLUEWIDTH - 1);
  5259.  
  5260.     /* our maximal width is far too big, so we try to make it narrower */
  5261.     w = max;
  5262.     j = (w & 1);        /* a pseudo-random bit */
  5263.     while (1) {
  5264.         while (physt[first] == 0)
  5265.             first++;
  5266.         while (physt[last] == 0)
  5267.             last--;
  5268.         if (last - first < (MAXBLUEWIDTH * 2 / 3) || (max - w) * 10 > max)
  5269.             break;
  5270.  
  5271.         if (physt[first] < physt[last]
  5272.             || physt[first] == physt[last] && j) {
  5273.             if (physt[first] * 20 > w)    /* if weight is >5%,
  5274.                              * stop */
  5275.                 break;
  5276.             w -= physt[first];
  5277.             first++;
  5278.             j = 0;
  5279.         } else {
  5280.             if (physt[last] * 20 > w)    /* if weight is >5%,
  5281.                              * stop */
  5282.                 break;
  5283.             w -= physt[last];
  5284.             last--;
  5285.             j = 1;
  5286.         }
  5287.     }
  5288.  
  5289.     /* save our zone */
  5290.     bluetab[0] = first - HYSTBASE;
  5291.     bluetab[1] = last - HYSTBASE;
  5292.  
  5293.     /* invalidate all the zones overlapping with this one */
  5294.     /* the constant of 2 is determined by the default value of BlueFuzz */
  5295.     for (i = first - (MAXBLUEWIDTH - 1) - 2; i <= last + 2; i++)
  5296.         if (i >= 0 && i < MAXHYST) {
  5297.             zhyst[i] = 0;
  5298.             ozhyst[i] = 0;
  5299.         }
  5300.     return w;
  5301. }
  5302.  
  5303. /*
  5304.  * Try to find the Blue Values, bounding box and italic angle
  5305.  */
  5306.  
  5307. void
  5308. findblues(void)
  5309. {
  5310.     /* hystograms for upper and lower zones */
  5311.     short           hystl[MAXHYST];
  5312.     short           hystu[MAXHYST];
  5313.     short           zuhyst[MAXHYST];
  5314.     short           zlhyst[MAXHYST];
  5315.     int             nchars;
  5316.     int             i, j, k, w, max;
  5317.     GENTRY         *ge;
  5318.     GLYPH          *g;
  5319.     double          ang;
  5320.  
  5321.     /* find the lowest and highest points of glyphs */
  5322.     /* and by the way build the values for FontBBox */
  5323.     /* and build the hystogram for the ItalicAngle */
  5324.  
  5325.     /* re-use hystl for the hystogram of italic angle */
  5326.  
  5327.     bbox[0] = bbox[1] = 5000;
  5328.     bbox[2] = bbox[3] = -5000;
  5329.  
  5330.     for (i = 0; i < MAXHYST; i++)
  5331.         hystl[i] = 0;
  5332.  
  5333.     nchars = 0;
  5334.  
  5335.     for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
  5336.         if (g->flags & GF_USED) {
  5337.             nchars++;
  5338.  
  5339.             g->rymin = 5000;
  5340.             g->rymax = -5000;
  5341.             for (ge = g->entries; ge != 0; ge = ge->next) {
  5342.                 if (ge->type == GE_LINE) {
  5343.  
  5344.                     j = ge->iy3 - ge->prev->iy3;
  5345.                     k = ge->ix3 - ge->prev->ix3;
  5346.                     if (j > 0)
  5347.                         ang = atan2(-k, j) * 180.0 / M_PI;
  5348.                     else
  5349.                         ang = atan2(k, -j) * 180.0 / M_PI;
  5350.  
  5351.                     k /= 100;
  5352.                     j /= 100;
  5353.                     if (ang > -45.0 && ang < 45.0) {
  5354.                         /*
  5355.                          * be careful to not overflow
  5356.                          * the counter
  5357.                          */
  5358.                         hystl[HYSTBASE + (int) (ang * 10.0)] += (k * k + j * j) / 4;
  5359.                     }
  5360.                     if (ge->iy3 == ge->prev->iy3) {
  5361.                         if (ge->iy3 <= g->rymin) {
  5362.                             g->rymin = ge->iy3;
  5363.                             g->flatymin = 1;
  5364.                         }
  5365.                         if (ge->iy3 >= g->rymax) {
  5366.                             g->rymax = ge->iy3;
  5367.                             g->flatymax = 1;
  5368.                         }
  5369.                     } else {
  5370.                         if (ge->iy3 < g->rymin) {
  5371.                             g->rymin = ge->iy3;
  5372.                             g->flatymin = 0;
  5373.                         }
  5374.                         if (ge->iy3 > g->rymax) {
  5375.                             g->rymax = ge->iy3;
  5376.                             g->flatymax = 0;
  5377.                         }
  5378.                     }
  5379.                 } else if (ge->type == GE_CURVE) {
  5380.                     if (ge->iy3 < g->rymin) {
  5381.                         g->rymin = ge->iy3;
  5382.                         g->flatymin = 0;
  5383.                     }
  5384.                     if (ge->iy3 > g->rymax) {
  5385.                         g->rymax = ge->iy3;
  5386.                         g->flatymax = 0;
  5387.                     }
  5388.                 }
  5389.                 if (ge->type == GE_LINE || ge->type == GE_CURVE) {
  5390.                     if (ge->ix3 < bbox[0])
  5391.                         bbox[0] = ge->ix3;
  5392.                     if (ge->ix3 > bbox[2])
  5393.                         bbox[2] = ge->ix3;
  5394.                     if (ge->iy3 < bbox[1])
  5395.                         bbox[1] = ge->iy3;
  5396.                     if (ge->iy3 > bbox[3])
  5397.                         bbox[3] = ge->iy3;
  5398.                 }
  5399.             }
  5400.         }
  5401.     }
  5402.  
  5403.     /* get the most popular angle */
  5404.     max = 0;
  5405.     w = 0;
  5406.     for (i = 0; i < MAXHYST; i++) {
  5407.         if (hystl[i] > w) {
  5408.             w = hystl[i];
  5409.             max = i;
  5410.         }
  5411.     }
  5412.     ang = (double) (max - HYSTBASE) / 10.0;
  5413.     WARNING_2 fprintf(stderr, "Guessed italic angle: %f\n", ang);
  5414.     if (italic_angle == 0.0)
  5415.         italic_angle = ang;
  5416.  
  5417.     /* build the hystogram of the lower points */
  5418.     for (i = 0; i < MAXHYST; i++)
  5419.         hystl[i] = 0;
  5420.  
  5421.     for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
  5422.         if ((g->flags & GF_USED)
  5423.             && g->rymin + HYSTBASE >= 0 && g->rymin < MAXHYST - HYSTBASE) {
  5424.             hystl[g->rymin + HYSTBASE]++;
  5425.         }
  5426.     }
  5427.  
  5428.     /* build the hystogram of the upper points */
  5429.     for (i = 0; i < MAXHYST; i++)
  5430.         hystu[i] = 0;
  5431.  
  5432.     for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
  5433.         if ((g->flags & GF_USED)
  5434.             && g->rymax + HYSTBASE >= 0 && g->rymax < MAXHYST - HYSTBASE) {
  5435.             hystu[g->rymax + HYSTBASE]++;
  5436.         }
  5437.     }
  5438.  
  5439.     /* build the hystogram of all the possible lower zones with max width */
  5440.     for (i = 0; i < MAXHYST; i++)
  5441.         zlhyst[i] = 0;
  5442.  
  5443.     for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
  5444.         for (j = 0; j < MAXBLUEWIDTH; j++)
  5445.             zlhyst[i] += hystl[i + j];
  5446.     }
  5447.  
  5448.     /* build the hystogram of all the possible upper zones with max width */
  5449.     for (i = 0; i < MAXHYST; i++)
  5450.         zuhyst[i] = 0;
  5451.  
  5452.     for (i = 0; i <= MAXHYST - MAXBLUEWIDTH; i++) {
  5453.         for (j = 0; j < MAXBLUEWIDTH; j++)
  5454.             zuhyst[i] += hystu[i + j];
  5455.     }
  5456.  
  5457.     /* find the baseline */
  5458.     w = bestblue(zlhyst, hystl, zuhyst, &bluevalues[0]);
  5459.     if (0)
  5460.         fprintf(stderr, "BaselineBlue zone %d%% %d...%d\n", w * 100 / nchars,
  5461.                 bluevalues[0], bluevalues[1]);
  5462.  
  5463.     if (w == 0)        /* no baseline, something weird */
  5464.         return;
  5465.  
  5466.     /* find the upper zones */
  5467.     for (nblues = 2; nblues < 14; nblues += 2) {
  5468.         w = bestblue(zuhyst, hystu, zlhyst, &bluevalues[nblues]);
  5469.  
  5470.         if (0)
  5471.             fprintf(stderr, "Blue zone %d%% %d...%d\n", w * 100 / nchars, 
  5472.                 bluevalues[nblues], bluevalues[nblues+1]);
  5473.  
  5474.         if (w * 20 < nchars)
  5475.             break;    /* don't save this zone */
  5476.     }
  5477.  
  5478.     /* find the lower zones */
  5479.     for (notherb = 0; notherb < 10; notherb += 2) {
  5480.         w = bestblue(zlhyst, hystl, zuhyst, &otherblues[notherb]);
  5481.  
  5482.         if (0)
  5483.             fprintf(stderr, "OtherBlue zone %d%% %d...%d\n", w * 100 / nchars,
  5484.                 otherblues[notherb], otherblues[notherb+1]);
  5485.  
  5486.  
  5487.         if (w * 20 < nchars)
  5488.             break;    /* don't save this zone */
  5489.     }
  5490.  
  5491. }
  5492.  
  5493. /*
  5494.  * Find the actual width of the glyph and modify the
  5495.  * description to reflect it. Not guaranteed to do
  5496.  * any good, may make character spacing too wide.
  5497.  */
  5498.  
  5499. void
  5500. docorrectwidth(void)
  5501. {
  5502.     int             i;
  5503.     GENTRY         *ge;
  5504.     GLYPH          *g;
  5505.     int             xmin, xmax;
  5506.     int             maxwidth, minsp;
  5507.  
  5508.     /* enforce this minimal spacing,
  5509.      * we limit the amount of the enforced spacing to avoid
  5510.      * spacing the bold wonts too widely
  5511.      */
  5512.     minsp = (stdhw>60 || stdhw<10)? 60 : stdhw;
  5513.  
  5514.     for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
  5515.         g->oldwidth=g->scaledwidth; /* save the old width, will need for AFM */
  5516.  
  5517.         if (correctwidth && g->flags & GF_USED) {
  5518.             xmin = 5000;
  5519.             xmax = -5000;
  5520.             for (ge = g->entries; ge != 0; ge = ge->next) {
  5521.                 if (ge->type != GE_LINE && ge->type != GE_CURVE) 
  5522.                     continue;
  5523.  
  5524.                 if (ge->ix3 <= xmin) {
  5525.                     xmin = ge->ix3;
  5526.                 }
  5527.                 if (ge->ix3 >= xmax) {
  5528.                     xmax = ge->ix3;
  5529.                 }
  5530.             }
  5531.  
  5532.             maxwidth=xmax+minsp;
  5533.             if( g->scaledwidth < maxwidth ) {
  5534.                 g->scaledwidth = maxwidth;
  5535.                 WARNING_3 fprintf(stderr, "glyph %s: extended from %d to %d\n",
  5536.                     g->name, g->oldwidth, g->scaledwidth );
  5537.             }
  5538.         }
  5539.     }
  5540.  
  5541. }
  5542.  
  5543. /*
  5544.  * Try to find the typical stem widths
  5545.  */
  5546.  
  5547. void
  5548. stemstatistics(void)
  5549. {
  5550. #define MINDIST    10 /* minimal distance between the widths */
  5551.     int             hyst[MAXHYST+MINDIST*2];
  5552.     int             best[12];
  5553.     int             i, j, k, w;
  5554.     int             nchars;
  5555.     int             ns;
  5556.     STEM           *s;
  5557.     GLYPH          *g;
  5558.  
  5559.     /* start with typical stem width */
  5560.  
  5561.     nchars=0;
  5562.  
  5563.     /* build the hystogram of horizontal stem widths */
  5564.     memset(hyst, 0, sizeof hyst);
  5565.  
  5566.     for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
  5567.         if (g->flags & GF_USED) {
  5568.             nchars++;
  5569.             s = g->hstems;
  5570.             for (j = 0; j < g->nhs; j += 2) {
  5571.                 if ((s[j].flags | s[j + 1].flags) & ST_END)
  5572.                     continue;
  5573.                 w = s[j + 1].value - s[j].value+1;
  5574.                 if(w==20) /* split stems should not be counted */
  5575.                     continue;
  5576.                 if (w > 0 && w < MAXHYST - 1) {
  5577.                     /*
  5578.                      * handle some fuzz present in
  5579.                      * converted fonts
  5580.                      */
  5581.                     hyst[w+MINDIST] += MINDIST-1;
  5582.                     for(k=1; k<MINDIST-1; k++) {
  5583.                         hyst[w+MINDIST + k] += MINDIST-1-k;
  5584.                         hyst[w+MINDIST - k] += MINDIST-1-k;
  5585.                     }
  5586.                 }
  5587.             }
  5588.         }
  5589.     }
  5590.  
  5591.     /* find 12 most frequent values */
  5592.     ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdhw);
  5593.  
  5594.     /* store data in stemsnaph */
  5595.     for (i = 0; i < ns; i++)
  5596.         stemsnaph[i] = best[i];
  5597.     if (ns < 12)
  5598.         stemsnaph[ns] = 0;
  5599.  
  5600.     /* build the hystogram of vertical stem widths */
  5601.     memset(hyst, 0, sizeof hyst);
  5602.  
  5603.     for (i = 0, g = glyph_list; i < numglyphs; i++, g++) {
  5604.         if (g->flags & GF_USED) {
  5605.             s = g->vstems;
  5606.             for (j = 0; j < g->nvs; j += 2) {
  5607.                 if ((s[j].flags | s[j + 1].flags) & ST_END)
  5608.                     continue;
  5609.                 w = s[j + 1].value - s[j].value+1;
  5610.                 if (w > 0 && w < MAXHYST - 1) {
  5611.                     /*
  5612.                      * handle some fuzz present in
  5613.                      * converted fonts
  5614.                      */
  5615.                     hyst[w+MINDIST] += MINDIST-1;
  5616.                     for(k=1; k<MINDIST-1; k++) {
  5617.                         hyst[w+MINDIST + k] += MINDIST-1-k;
  5618.                         hyst[w+MINDIST - k] += MINDIST-1-k;
  5619.                     }
  5620.                 }
  5621.             }
  5622.         }
  5623.     }
  5624.  
  5625.     /* find 12 most frequent values */
  5626.     ns = besthyst(hyst+MINDIST, 0, best, 12, MINDIST, &stdvw);
  5627.  
  5628.     /* store data in stemsnaph */
  5629.     for (i = 0; i < ns; i++)
  5630.         stemsnapv[i] = best[i];
  5631.     if (ns < 12)
  5632.         stemsnapv[ns] = 0;
  5633.  
  5634. #undef MINDIST
  5635. }
  5636.  
  5637. /*
  5638.  * SB
  5639.  * A funny thing: TTF paths are going in reverse direction compared
  5640.  * to Type1. So after all (because the rest of logic uses TTF
  5641.  * path directions) we have to reverse the paths.
  5642.  *
  5643.  * It was a big headache to discover that.
  5644.  */
  5645.  
  5646. /* works on both int and float paths */
  5647.  
  5648. void
  5649. reversepathsfromto(
  5650.            GENTRY * from,
  5651.            GENTRY * to
  5652. )
  5653. {
  5654.     GENTRY         *ge, *nge, *pge;
  5655.     GENTRY         *cur, *next;
  5656.     int i, n, ilast[2];
  5657.     double flast[2], f;
  5658.  
  5659.     for (ge = from; ge != 0 && ge != to; ge = ge->next) {
  5660.         if(ge->type == GE_LINE || ge->type == GE_CURVE) {
  5661.             if (ISDBG(REVERSAL))
  5662.                 fprintf(stderr, "reverse path 0x%x <- 0x%x, 0x%x\n", ge, ge->prev, ge->bkwd);
  5663.  
  5664.             /* cut out the path itself */
  5665.             pge = ge->prev; /* GE_MOVE */
  5666.             if (pge == 0) {
  5667.                 fprintf(stderr, "**! No MOVE before line !!! Fatal. ****\n");
  5668.                 exit(1);
  5669.             }
  5670.             nge = ge->bkwd->next; /* GE_PATH */
  5671.             pge->next = nge;
  5672.             nge->prev = pge;
  5673.             ge->bkwd->next = 0; /* mark end of chain */
  5674.  
  5675.             /* remember the starting point */
  5676.             if(ge->flags & GEF_FLOAT) {
  5677.                 flast[0] = pge->fx3;
  5678.                 flast[1] = pge->fy3;
  5679.             } else {
  5680.                 ilast[0] = pge->ix3;
  5681.                 ilast[1] = pge->iy3;
  5682.             }
  5683.  
  5684.             /* then reinsert them in backwards order */
  5685.             for(cur = ge; cur != 0; cur = next ) {
  5686.                 next = cur->next; /* or addgeafter() will screw it up */
  5687.                 if(cur->flags & GEF_FLOAT) {
  5688.                     for(i=0; i<2; i++) {
  5689.                         /* reverse the direction of path element */
  5690.                         f = cur->fpoints[i][0];
  5691.                         cur->fpoints[i][0] = cur->fpoints[i][1];
  5692.                         cur->fpoints[i][1] = f;
  5693.                         f = flast[i];
  5694.                         flast[i] = cur->fpoints[i][2];
  5695.                         cur->fpoints[i][2] = f;
  5696.                     }
  5697.                 } else {
  5698.                     for(i=0; i<2; i++) {
  5699.                         /* reverse the direction of path element */
  5700.                         n = cur->ipoints[i][0];
  5701.                         cur->ipoints[i][0] = cur->ipoints[i][1];
  5702.                         cur->ipoints[i][1] = n;
  5703.                         n = ilast[i];
  5704.                         ilast[i] = cur->ipoints[i][2];
  5705.                         cur->ipoints[i][2] = n;
  5706.                     }
  5707.                 }
  5708.                 addgeafter(pge, cur);
  5709.             }
  5710.  
  5711.             /* restore the starting point */
  5712.             if(ge->flags & GEF_FLOAT) {
  5713.                 pge->fx3 = flast[0];
  5714.                 pge->fy3 = flast[1];
  5715.             } else {
  5716.                 pge->ix3 = ilast[0];
  5717.                 pge->iy3 = ilast[1];
  5718.             }
  5719.  
  5720.             ge = nge;
  5721.         }
  5722.  
  5723.     }
  5724. }
  5725.  
  5726. void
  5727. reversepaths(
  5728.          GLYPH * g
  5729. )
  5730. {
  5731.     reversepathsfromto(g->entries, NULL);
  5732. }
  5733.  
  5734. /* add a kerning pair information, scales the value */
  5735.  
  5736. void
  5737. addkernpair(
  5738.     unsigned id1,
  5739.     unsigned id2,
  5740.     int unscval
  5741. )
  5742. {
  5743.     static unsigned char *bits = 0;
  5744.     static int lastid;
  5745.     GLYPH *g = &glyph_list[id1];
  5746.     int i, n;
  5747.     struct kern *p;
  5748.  
  5749.     if(unscval == 0 || id1 >= numglyphs || id2 >= numglyphs)
  5750.         return;
  5751.  
  5752.     if( (glyph_list[id1].flags & GF_USED)==0
  5753.     || (glyph_list[id2].flags & GF_USED)==0 )
  5754.         return;
  5755.  
  5756.     if(bits == 0) {
  5757.         bits = calloc( BITMAP_BYTES(numglyphs), 1);
  5758.         if (bits == NULL) {
  5759.             fprintf (stderr, "****malloc failed %s line %d\n", __FILE__, __LINE__);
  5760.             exit(255);
  5761.         }
  5762.         lastid = id1;
  5763.     }
  5764.  
  5765.     if(lastid != id1) {
  5766.         /* refill the bitmap cache */
  5767.         memset(bits, 0,BITMAP_BYTES(numglyphs));
  5768.         p = g->kern;
  5769.         for(i=g->kerncount; i>0; i--) {
  5770.             n = (p++)->id;
  5771.             SET_BITMAP(bits, n);
  5772.         }
  5773.         lastid = id1;
  5774.     }
  5775.  
  5776.     if(IS_BITMAP(bits, id2))
  5777.         return; /* duplicate */
  5778.  
  5779.     if(g->kerncount <= g->kernalloc) {
  5780.         g->kernalloc += 8;
  5781.         p = realloc(g->kern, sizeof(struct kern) * g->kernalloc);
  5782.         if(p == 0) {
  5783.             fprintf (stderr, "** realloc failed, kerning data will be incomplete\n");
  5784.         }
  5785.         g->kern = p;
  5786.     }
  5787.  
  5788.     SET_BITMAP(bits, id2);
  5789.     p = &g->kern[g->kerncount];
  5790.     p->id = id2;
  5791.     p->val = iscale(unscval) - (g->scaledwidth - g->oldwidth);
  5792.     g->kerncount++;
  5793.     kerning_pairs++;
  5794. }
  5795.  
  5796. /* print out the kerning information */
  5797.  
  5798. void
  5799. print_kerning(
  5800.     FILE *afm_file
  5801. )
  5802. {
  5803.     int    i, j, n;
  5804.     GLYPH *g;
  5805.     struct kern *p;
  5806.  
  5807.     if( kerning_pairs == 0 ) 
  5808.         return;
  5809.  
  5810.     fprintf(afm_file, "StartKernData\n");
  5811.     fprintf(afm_file, "StartKernPairs %hd\n", kerning_pairs);
  5812.  
  5813.     for(i=0; i<numglyphs; i++)  {
  5814.         g = &glyph_list[i];
  5815.         if( (g->flags & GF_USED) ==0)
  5816.             continue;
  5817.         p = g->kern;
  5818.         for(j=g->kerncount; j>0; j--, p++) {
  5819.             fprintf(afm_file, "KPX %s %s %d\n", g->name, 
  5820.                 glyph_list[ p->id ].name, p->val );
  5821.         }
  5822.     }
  5823.  
  5824.     fprintf(afm_file, "EndKernPairs\n");
  5825.     fprintf(afm_file, "EndKernData\n");
  5826. }
  5827.  
  5828.  
  5829. #if 0
  5830.  
  5831. /*
  5832. ** This function is commented out because the information
  5833. ** collected by it is not used anywhere else yet. Now
  5834. ** it only collects the directions of contours. And the
  5835. ** direction of contours gets fixed already in draw_glyf().
  5836. **
  5837. ***********************************************
  5838. **
  5839. ** Here we expect that the paths are already closed.
  5840. ** We also expect that the contours do not intersect
  5841. ** and that curves doesn't cross any border of quadrant.
  5842. **
  5843. ** Find which contours go inside which and what is
  5844. ** their proper direction. Then fix the direction
  5845. ** to make it right.
  5846. **
  5847. */
  5848.  
  5849. #define MAXCONT    1000
  5850.  
  5851. void
  5852. fixcontours(
  5853.         GLYPH * g
  5854. )
  5855. {
  5856.     CONTOUR         cont[MAXCONT];
  5857.     short           ymax[MAXCONT];    /* the highest point */
  5858.     short           xofmax[MAXCONT];    /* X-coordinate of any point
  5859.                          * at ymax */
  5860.     short           ymin[MAXCONT];    /* the lowest point */
  5861.     short           xofmin[MAXCONT];    /* X-coordinate of any point
  5862.                          * at ymin */
  5863.     short           count[MAXCONT];    /* count of lines */
  5864.     char            dir[MAXCONT];    /* in which direction they must go */
  5865.     GENTRY         *start[MAXCONT], *minptr[MAXCONT], *maxptr[MAXCONT];
  5866.     int             ncont;
  5867.     int             i;
  5868.     int             dx1, dy1, dx2, dy2;
  5869.     GENTRY         *ge, *nge;
  5870.  
  5871.     /* find the contours and their most upper/lower points */
  5872.     ncont = 0;
  5873.     ymax[0] = -5000;
  5874.     ymin[0] = 5000;
  5875.     for (ge = g->entries; ge != 0; ge = ge->next) {
  5876.         if (ge->type == GE_LINE || ge->type == GE_CURVE) {
  5877.             if (ge->iy3 > ymax[ncont]) {
  5878.                 ymax[ncont] = ge->iy3;
  5879.                 xofmax[ncont] = ge->ix3;
  5880.                 maxptr[ncont] = ge;
  5881.             }
  5882.             if (ge->iy3 < ymin[ncont]) {
  5883.                 ymin[ncont] = ge->iy3;
  5884.                 xofmin[ncont] = ge->ix3;
  5885.                 minptr[ncont] = ge;
  5886.             }
  5887.         }
  5888.         if (ge->frwd != ge->next) {
  5889.             start[ncont++] = ge->frwd;
  5890.             ymax[ncont] = -5000;
  5891.             ymin[ncont] = 5000;
  5892.         }
  5893.     }
  5894.  
  5895.     /* determine the directions of contours */
  5896.     for (i = 0; i < ncont; i++) {
  5897.         ge = minptr[i];
  5898.         nge = ge->frwd;
  5899.  
  5900.         if (ge->type == GE_CURVE) {
  5901.             dx1 = ge->ix3 - ge->ix2;
  5902.             dy1 = ge->iy3 - ge->iy2;
  5903.  
  5904.             if (dx1 == 0 && dy1 == 0) {    /* a pathological case */
  5905.                 dx1 = ge->ix3 - ge->ix1;
  5906.                 dy1 = ge->iy3 - ge->iy1;
  5907.             }
  5908.             if (dx1 == 0 && dy1 == 0) {    /* a more pathological
  5909.                              * case */
  5910.                 dx1 = ge->ix3 - ge->prev->ix3;
  5911.                 dy1 = ge->iy3 - ge->prev->iy3;
  5912.             }
  5913.         } else {
  5914.             dx1 = ge->ix3 - ge->prev->ix3;
  5915.             dy1 = ge->iy3 - ge->prev->iy3;
  5916.         }
  5917.         if (nge->type == GE_CURVE) {
  5918.             dx2 = ge->ix3 - nge->ix1;
  5919.             dy2 = ge->iy3 - nge->iy1;
  5920.             if (dx1 == 0 && dy1 == 0) {    /* a pathological case */
  5921.                 dx2 = ge->ix3 - nge->ix2;
  5922.                 dy2 = ge->iy3 - nge->iy2;
  5923.             }
  5924.             if (dx1 == 0 && dy1 == 0) {    /* a more pathological
  5925.                              * case */
  5926.                 dx2 = ge->ix3 - nge->ix3;
  5927.                 dy2 = ge->iy3 - nge->iy3;
  5928.             }
  5929.         } else {
  5930.             dx2 = ge->ix3 - nge->ix3;
  5931.             dy2 = ge->iy3 - nge->iy3;
  5932.         }
  5933.  
  5934.         /* compare angles */
  5935.         cont[i].direction = DIR_INNER;
  5936.         if (dy1 == 0) {
  5937.             if (dx1 < 0)
  5938.                 cont[i].direction = DIR_OUTER;
  5939.         } else if (dy2 == 0) {
  5940.             if (dx2 > 0)
  5941.                 cont[i].direction = DIR_OUTER;
  5942.         } else if (dx2 * dy1 < dx1 * dy2)
  5943.             cont[i].direction = DIR_OUTER;
  5944.  
  5945.         cont[i].ymin = ymin[i];
  5946.         cont[i].xofmin = xofmin[i];
  5947.     }
  5948.  
  5949.     /* save the information that may be needed further */
  5950.     g->ncontours = ncont;
  5951.     if (ncont > 0) {
  5952.         g->contours = malloc(sizeof(CONTOUR) * ncont);
  5953.         if (g->contours == 0) {
  5954.             fprintf(stderr, "***** Memory allocation error *****\n");
  5955.             exit(255);
  5956.         }
  5957.         memcpy(g->contours, cont, sizeof(CONTOUR) * ncont);
  5958.     }
  5959. }
  5960.  
  5961. #endif
  5962.  
  5963. /*
  5964.  *
  5965.  */
  5966.  
  5967.